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.
