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.


1 Answer 1


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). 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.

  • $\begingroup$ 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... $\endgroup$
    – Vanessa
    Commented Sep 16, 2018 at 12:02
  • 1
    $\begingroup$ @Squark In the conclusion section, they mention that the same construction works for the depth version as well. $\endgroup$
    – zeb
    Commented Sep 16, 2018 at 23:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.