Is Bayes optimal RL of a finite set of DFAs feasible?
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.