<p>Even determining whether there is a policy which always succeeds is NP-complete, by a reduction from constructing optimal decision trees (<a href="https://people.csail.mit.edu/rivest/pubs/HR76.pdf" rel="nofollow noreferrer">Hyafil and Rivest, Constructing Optimal Binary Decision Trees is NP-complete</a>). We interpret the word <span class="math-container">$w$</span> as a sequence of <span class="math-container">$m-1$</span> yes/no questions about <span class="math-container">$k$</span>, drawn from a list of allowed questions, followed by a guess for the value of <span class="math-container">$k$</span>. It's easy to construct state machines <span class="math-container">$\delta_k$</span> which keep a counter of how many questions have been asked so far together with the answer to the most recent question asked as their state, and then accept or reject based on whether the guess at the end is correct.</p>

CC BY-SA 4.0
2018-09-16T12:02:22.907Z
Thank you very much! There is only one issue here, namely that in Hyafil and Rivest the problem is deciding whether there is a decision tree with given *external path length* whereas this reduction seems to refer to the problem of deciding whether there is a decision three of given *depth*. On the other hand, I *think* that the reduction of 3-Exact Cover that Hyafil and Rivest construct works for the depth version too...
Vanessa
CC BY-SA 4.0
2018-09-16T23:02:17.663Z
@Squark In the conclusion section, they mention that the same construction works for the depth version as well.
zeb
CC BY-SA 4.0
2018-09-16T08:12:15.900Z
2023-08-30T12:29:34.927Z
2023-08-30T12:29:34.927Z
zeb
<p>Let $Q$ be a finite set of states, $\Sigma$ a finite alphabet, $q_0\in Q$ the start state and $F\subseteq Q$ the set of accepting sets. Let $\{\delta_k:Q\times\Sigma\rightarrow Q\}_{k=1}^n$ be a set of $n$ possible transition functions and $m$ a fixed natural number. Consider the following problem: find a word $w\in\Sigma^m$ s.t. the DFA accepts $w$ with maximal probability, assuming that the transition function is chosen randomly from a uniform distribution over the $\delta_k$, and that you are allowed to observe the state transitions resulting from $w_1\ldots w_k$ before choosing $w_{k+1}$ (but you don't know which transition function was chosen). In other words, we are doing one-shot reinforcement learning for a deterministic MDP where $\Sigma$ is the set of actions, and the reward is $1$ if we end up in $F$ after $m$ actions and $0$ otherwise.</p>

<p>Given a policy $\pi: (\Sigma \times Q)^{&lt; m} \rightarrow \Sigma$ (that decides which action to take after observing a given history), and some choice of $\delta_k$, we get a particular history $h_{\pi,k}\in(\Sigma\times Q)^{m}$. In fact, the collection of the $h_{\pi,k}$ for $k$ from $1$ to $n$ gives us a <em>compact description</em> of $\pi$: in order to implement $\pi$, we just need to look at the current history $h\in(\Sigma \times Q)^{&lt; m}$ and find $k$ s.t. $h$ is a prefix of $h_{\pi,k}$ to know what action to take next. This description is of size $O(nm|\Sigma||Q|)$, as opposed to a lookup table for $\pi$ which would be of size exponential in $m$. In particular, an <em>optimal</em> policy (i.e. a policy which maximizes the probability of the DFA accepting) also has such a compact description.</p>

<p><strong>Is it possible to find a compact description (as above) of an optimal policy in time polynomial in the size of the problem and $m$?</strong></p>

<p>Here I'm assuming that the $\delta_k$ are given explicitly as lookup tables, and $F$ as a list of states (where states and actions are represented by numbers). For a negative answer, you can assume any standard complexity-theory conjecture.</p>

<cc.complexity-theory><lg.learning><dfa><reinforcement-learning>
Is Bayes optimal RL of a finite set of DFAs feasible?
Vanessa
# Is Bayes optimal RL of a finite set of DFAs feasible?

(Asked by: username_0 on 2018-08-18)

Let $Q$ be a finite set of states, $\Sigma$ a finite alphabet, $q\_0\in Q$ the start state and $F\subseteq Q$ the set of accepting sets. Let $\{\delta\_k:Q\times\Sigma\rightarrow Q\}\_{k=1}^n$ be a set of $n$ possible transition functions and $m$ a fixed natural number. Consider the following problem: find a word $w\in\Sigma^m$ s.t. the DFA accepts $w$ with maximal probability, assuming that the transition function is chosen randomly from a uniform distribution over the $\delta\_k$, and that you are allowed to observe the state transitions resulting from $w\_1\ldots w\_k$ before choosing $w\_{k+1}$ (but you don't know which transition function was chosen). In other words, we are doing one-shot reinforcement learning for a deterministic MDP where $\Sigma$ is the set of actions, and the reward is $1$ if we end up in $F$ after $m$ actions and $0$ otherwise.

Given a policy $\pi: (\Sigma \times Q)^{< m} \rightarrow \Sigma$ (that decides which action to take after observing a given history), and some choice of $\delta\_k$, we get a particular history $h\_{\pi,k}\in(\Sigma\times Q)^{m}$. In fact, the collection of the $h\_{\pi,k}$ for $k$ from $1$ to $n$ gives us a *compact description* of $\pi$: in order to implement $\pi$, we just need to look at the current history $h\in(\Sigma \times Q)^{< m}$ and find $k$ s.t. $h$ is a prefix of $h\_{\pi,k}$ to know what action to take next. This description is of size $O(nm|\Sigma||Q|)$, as opposed to a lookup table for $\pi$ which would be of size exponential in $m$. In particular, an *optimal* policy (i.e. a policy which maximizes the probability of the DFA accepting) also has such a compact description.

**Is it possible to find a compact description (as above) of an optimal policy in time polynomial in the size of the problem and $m$?**

Here I'm assuming that the $\delta\_k$ are given explicitly as lookup tables, and $F$ as a list of states (where states and actions are represented by numbers). For a negative answer, you can assume any standard complexity-theory conjecture.

**Tags:** cc.complexity-theory, lg.learning, dfa, reinforcement-learning


---

## 1 answers

### Answer by username_1 on 2018-09-16. Score: 3 | Accepted answer

Even determining whether there is a policy which always succeeds is NP-complete, by a reduction from constructing optimal decision trees ([Hyafil and Rivest, Constructing Optimal Binary Decision Trees is NP-complete](https://people.csail.mit.edu/rivest/pubs/HR76.pdf)). We interpret the word $w$ as a sequence of $m-1$ yes/no questions about $k$, drawn from a list of allowed questions, followed by a guess for the value of $k$. It's easy to construct state machines $\delta\_k$ which keep a counter of how many questions have been asked so far together with the answer to the most recent question asked as their state, and then accept or reject based on whether the guess at the end is correct.

> **Comments:**
> **username_0**: Thank you very much! There is only one issue here, namely that in Hyafil and Rivest the problem is deciding whether there is a decision tree with given *external path length* whereas this reduction seems to refer to the problem of deciding whether there is a decision three of given *depth*. On the other hand, I *think* that the reduction of 3-Exact Cover that Hyafil and Rivest construct works for the depth version too...  
> **username_1**: @Squark In the conclusion section, they mention that the same construction works for the depth version as well.  

---

