# Is Bayes optimal RL of a finite set of DFAs feasible?

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.

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.