Complexity of finite-state partial information games

Question

Given a deterministic partial-information zero-sum game with only finitely many states,
whose possible outcomes are [lose,draw,win] with values [-1,0,+1] respectively,
what is the complexity of approximating the value of such a game additively within $\epsilon$?

In particular, I can't come up any algorithm whatsoever for doing that.
The rest of this post is devoted entirely to giving a more thorough description
of the problem, so if you can already figure out what the question at the top
of this post means, then there's no reason for you to read the rest of this post.

Given a referee machine with states $\{1,2,3,...,S\}$, with a designated initial state $s_0$, a state $s_a$ whose score pair is $[-1,+1]$, a state $s_b$ whose score pair is $[+1,-1]$, and states of the form

$[\mbox{p1_info,p2_info,num_of_choices,player_to_move,next_state_table}]$ where:

• $\mbox{player_to_move} \in \{1,2\}$
• $\mbox{next_state_table}$ is a function from $\{1,2,3,...,\mbox{num_of_choices}\} \to \{1,2,3,...,S\}$
• $\mbox{p1_info},\mbox{p2_info}, \mbox{num_of_choices} \geq 1$

When the machine is in a state of that form:

• sends $\mbox{p1_info}$ to Player_1 and sends $\mbox{p2_info}$ to Player_2,
• sends $\mbox{num_of_choices}$ to the indicated player, waits for an element of $\{1,2,3,...,\mbox{num_of_choices}\}$ as input from that player,
• then goes to the state indicated by $\mbox{next_state_table}$

When the machine enters one of the other two states $s_a$ or $s_b$,

• halts with that state's score pair as its output

There is a natural two-player game: the referee machine is started in state $s_0 = 1$,
the players provide the inputs that the referee machine waits for, if the referee machine
halts then Player 1 scores the first value of the machine's output pair and Player 2
scores the second value of the machine's output pair, otherwise both players score 0.

What is the complexity of the following problem?
Given such a referee machine and a positive integer N, output a rational number
that is (additively) within 1/N of the value of the natural game for Player 1.

As mentioned earlier in this question, I can't come
up with any algorithm whatsoever for doing that.

Answer 1

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.

Answer 2

By Theorem 3.1 and the proof's IPS being one-way,
for all real numbers $\epsilon$, if ​ $0<\epsilon$ ​ then the promise problem

Input: ​ a game as described in my question
must output YES if : ​ ​ ​ the game's value for Player 1 is greater than 1-$\hspace{.025 in}\epsilon$
must output ​ NO ​ if : ​ ​ ​ the game's value for Player 1 is less than $\epsilon$

remains RE-hard even when

player_to_move is always 1 ​ (i.e., only 1 player is needed)
and
s₀ ≠ s_a ​ and ​ s_a is not in Range(next_state_table)
(i.e., it's literally impossible for the player to lose)
and
p1_info and p2_info and number_of_choices are independent of the state
(i.e., the player's only feedback is whether or not it just won)

.