Complexity of finite-state partial information games
NOTE: my purported algorithm was incorrect; I deleted it. 

One thing to realize is that it doesn't matter whether the game is deterministic or not. To randomize, the referee can ask each of the players to contribute a random number mod $p$, and then add them. It's easy to show that if the players use their optimal strategy, the sum is a random number mod $p$, which the referee can then use to randomize his strategy. This doesn't greatly increase the number of states in the game. 

For a lower bound on the complexity, the question of approximating the value of a simple stochastic game is not known to be in P. Using the randomization trick I gave above, it is easy to write a simple stochastic game as a refereed game with a polynomial-size lookup table.