Surprisingly, approximate win probability for one-player games with randomness and 3 bits of hidden state (in addition to non-hidden state; rational transition probabilities) is uncomputable.

Question: Do 2 bits of hidden state suffice for the undecidability?

3-bit undecidability

For 3-bit hidden state, here is a reduction from the halting problem. The general argument (undecidability of POMDP) is not new; I do not know whether the 3 bit result is new.

Winning game instances will have $> 1-ε_1$ win probability and losing instances $< ε_2$. $ε_1$ can be made arbitrarily small by the player. $ε_2$ can be made arbitrarily small by increasing non-hidden state size or changing transition probabilities. The non-hidden state evolution is deterministic and unaffected by the hidden state. Non-hidden state size can be made independent of the Turing machine by encoding the machine through a special instruction to set hidden state probabilities ( (increment_counter c)* below).

Game lengths: In the reduction, expected game length is $(ε_1ε_2)^{-T^{O(1)}}$ where $T$ is the halting time for a nondeterministic 2-counter automaton (used as the halting problem instance; instance-independent non-hidden state size uses a single automaton but varies initial counter size). Additional $O(1)$ hidden state would allow a nondeterministic $k$-counter automaton (not sure if nondeterministic 2-counters can simulate them in polynomial time), allowing $T=2^{O(S)}$ (and thus expected game length $2^{2^{O(S)}}$ for constant $ε_1$ and $ε_2$) where $S$ is space usage (plus input size) of the desired nondeterministic Turing machine. I suspect that is optimal, so simulation of Turing machines by these games is very slow.

The trick to undecidability is that the closeness of a probability to 0 can be used somewhat like a counter, with conditional probabilities allowing either a measurement, or a reset, allowing one to try again with new input. (However, this also gives two-sided error, and nonrobustness against slightly non-independent coin flip probabilities.) For example, to test $a=b$ in a stream $1^a 0 1^b$, we can set hidden $x$ to 1 with probability $2^{-a-b-1}$ and to 2 with probability $2^{-2a-2}$ and to 3 with probability $2^{-2b-2}$, and thus conditional on $x$ being 1 or 2 or 3, $x=1$ is evidence that $a=b$. This can be generalized to test $a_1=a_2 ∧ b_1=b_ 2 ∧ ...$ in $1^{a_1} 0 1^{a_2} 0 1^{b_1} 0 1^{b_2} 0 ...$ by randomly switching between 2 and 3 (i.e. if $x$ is 2 or 3, then with 50% probability set $x := 5-x$) after each variable pair is read.

Our full hidden state machine uses states 0, 1, 11, 12, 21, 22, Lose, Win (0, Lose, and Win need not be hidden), and can receive the following commands:
start: Start at state 0.
choose_path: If not in state Lose or Win, go to 1 with probability 1/2 and to 11,12,21,22 with probability 1/8 each.
increment_counter c: If in state c (other than 0, Win, or Lose), with probability 1/2 go to 0.
next_counter i: If in state ij, choose randomly between state i1 and i2.
end_or_reset: If in state 1, go to Win, and if in state 11, 12, 21, or 22, go to Lose.

For the reduction from the halting problem, the player will simulate the Turing machine using an appropriate counter program, and send (run* stop)*, where run is the history of the counter machine, with the counter(s) printed in unary at each step. The non-hidden state will act as a finite state transducer converting each (run* stop) into choose_path (increment_counter c | next_counter i)* end_or_reset. The number of repetitions in each run* (run* means run is repeated zero or more times) is chosen by the player to reduce false negatives, while (run* stop) is repeated until reaching Win or Lose (the transition to Win/Lose ordinarily has probability $2^{-θ(|\text{(run* stop)}|)}$ (for a fixed game)).

The counter machine can have one counter, plus the ability to multiply and divide (with remainder) by fixed small numbers (2, 3, etc), which corresponds to a 2-counter machine with us storing only the steps when one of the counters is 0. Verifying the run consists of verifying the syntax, plus testing of counter value transitions. Let $c_k$ be increment_counter k. The number of $c_1$ calls will be proportional to the sum of all counter values; $c_{1j}$ can verify odd numbered (i.e. occurring at time step 1, 3, 5, ...) transitions of counter values, and $c_{2j}$ even numbered, with $c_{i1}$ and $c_{i2}$ used analogously to $x=2$ and $x=3$ above.

2-EXPTIME version

As an aside, for polynomial size hidden state, existence of a strategy with win probability 1 is I think 2-EXPTIME complete. For 2-EXPTIME hardness, we only need to distinguish probability 1 from $<ε$, and after setting the hidden state, we only need public coin randomness. Using the hidden state and hashing, we can force the player to manipulate an imaginary exponential length tape (while storing its updatable hash). Using randomness, we can then set up a triple exponential expected number of runs to simulate an opponent and get 2-EXPTIME hardness. Without randomness after initially setting the hidden state, the problem is EXPSPACE complete. It would be interesting to have a large table giving the complexity class for various combinations of randomness, hidden state, opponents, and completeness.

  • $\begingroup$ The problem with reducing 5 hidden states to 4 is that we appear to need one state to indicate the current likelihood of the accepting path, while for the rejecting path we need to store both whether we are penalizing the counter value being too large vs penalizing being too small, and whether we are compensating for the previous test. $\endgroup$ Commented Feb 10 at 18:36
  • $\begingroup$ A variation on the above state machine is to add swap i: swap i0 with i1, which eliminates the need for increment_counter 12 and increment_counter 22. This way we get undecidability (of approximate win probability) for deterministic two player games with hidden alternating moves and 3-bits of hidden state: A fair coin for the system can be implemented by doubling states 1, 11, and 21. $\endgroup$ Commented Feb 10 at 18:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.