<p>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.</p>
<p><b>Question:</b>  Do 2 bits of hidden state suffice for the undecidability?</p>
<p><b>3-bit undecidability</b></p>
<p>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.</p>
<p>Winning game instances will have <span class="math-container">$&gt; 1-ε_1$</span> win probability and losing instances <span class="math-container">$&lt; ε_2$</span>. <span class="math-container">$ε_1$</span> can be made arbitrarily small by the player.  <span class="math-container">$ε_2$</span> 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 ( <code>(increment_counter c)*</code> below).</p>
<p><em>Game lengths</em>:  In the reduction, expected game length is <span class="math-container">$(ε_1ε_2)^{-T^{O(1)}}$</span> where <span class="math-container">$T$</span> 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 <span class="math-container">$O(1)$</span> hidden state would allow a nondeterministic <span class="math-container">$k$</span>-counter automaton (not sure if nondeterministic 2-counters can simulate them in polynomial time), allowing <span class="math-container">$T=2^{O(S)}$</span> (and thus expected game length <span class="math-container">$2^{2^{O(S)}}$</span> for constant <span class="math-container">$ε_1$</span> and <span class="math-container">$ε_2$</span>) where <span class="math-container">$S$</span> 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.</p>
<p>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 <span class="math-container">$a=b$</span> in a stream <span class="math-container">$1^a 0 1^b$</span>, we can set hidden <span class="math-container">$x$</span> to 1 with probability <span class="math-container">$2^{-a-b-1}$</span> and to 2 with probability <span class="math-container">$2^{-2a-2}$</span> and to 3 with probability <span class="math-container">$2^{-2b-2}$</span>, and thus conditional on <span class="math-container">$x$</span> being 1 or 2 or 3, <span class="math-container">$x=1$</span> is evidence that <span class="math-container">$a=b$</span>.  This can be generalized to test <span class="math-container">$a_1=a_2 ∧ b_1=b_ 2 ∧ ...$</span> in <span class="math-container">$1^{a_1} 0 1^{a_2} 0 1^{b_1} 0 1^{b_2} 0 ...$</span> by randomly switching between 2 and 3 (i.e. if <span class="math-container">$x$</span> is 2 or 3, then with 50% probability set <span class="math-container">$x := 5-x$</span>) after each variable pair is read.</p>
<p>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:<br/>
<code>start</code>: Start at state 0.<br/>
<code>choose_path</code>: 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.<br/>
<code>increment_counter c</code>: If in state c (other than 0, Win, or Lose), with probability 1/2 go to 0.<br/>
<code>next_counter i</code>: If in state ij, choose randomly between state i1 and i2.<br/>
<code>end_or_reset</code>: If in state 1, go to Win, and if in state 11, 12, 21, or 22, go to Lose.</p>
<p>For the reduction from the halting problem, the player will simulate the Turing machine using an appropriate counter program, and send <code>(run* stop)*</code>, where <code>run</code> 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 <code>(run* stop)</code> into <code>choose_path (increment_counter c | next_counter i)* end_or_reset</code>.  The number of repetitions in each <code>run*</code> (<code>run*</code> means <code>run</code> is repeated zero or more times) is chosen by the player to reduce false negatives, while <code>(run* stop)</code> is repeated until reaching Win or Lose (the transition to Win/Lose ordinarily has probability <span class="math-container">$2^{-θ(|\text{(run* stop)}|)}$</span> (for a fixed game)).</p>
<p>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 <span class="math-container">$c_k$</span> be <code>increment_counter k</code>. The number of <span class="math-container">$c_1$</span> calls will be proportional to the sum of all counter values; <span class="math-container">$c_{1j}$</span> can verify odd numbered (i.e. occurring at time step 1, 3, 5, ...) transitions of counter values, and <span class="math-container">$c_{2j}$</span> even numbered, with <span class="math-container">$c_{i1}$</span> and <span class="math-container">$c_{i2}$</span> used analogously to <span class="math-container">$x=2$</span> and <span class="math-container">$x=3$</span> above.</p>
<p><b>2-EXPTIME version</b></p>
<p>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 <span class="math-container">$&lt;ε$</span>, 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.</p>

CC BY-SA 4.0
2024-02-10T18:36:05.350Z
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.
Dmytro Taranovsky
CC BY-SA 4.0
2024-02-10T18:39:38.400Z
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.
Dmytro Taranovsky
<cc.complexity-theory><gt.game-theory><decidability><markov-processes>
Undecidability of games with limited hidden state
Dmytro Taranovsky
# Undecidability of games with limited hidden state

(Asked by: username_0 on 2024-02-08)

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.

**Tags:** cc.complexity-theory, gt.game-theory, decidability, markov-processes

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  

---

## 0 answers

