Consider a set of $n$ MDPs (Markov decision processes). An MDP $M$ is selected from this set according to some probability distribution $\xi$ and then interacts with a fixed policy $\pi$ for time $T$ yielding a total expected reward of $V_\pi$ (where the expectation value is w.r.t. $\xi$, the random transitions in $M$ and possibly random decisions by $\pi$). The problem of designing a policy such that $V_\pi$ is as high as possible is known as reinforcement learning (specifically, we only consider here the special case of model-based Bayesian reinforcement learning with a finite set of $n$ models). A policy $\pi$ for which $V_\pi$ equals the highest possible value $V^*$ is said to be Bayes optimal.

It is often claimed that computing a Bayes optimal policy is intractable, therefore we need to use algorithms that are not Bayes optimal but still satisfy good performance bounds (e.g. PSRL or some UCB algorithm). However, I am not sure to which extent this intractability is backed by complexity theoretic hardness theorems?

In fact, this kind of reinforcement learning can be regarded as a special case of solving a POMDP (partially observable Markov decision process). Namely, we can consider a POMDP $\hat{M}$ in which a random transition at the initial state samples $\xi$ in a manner which is unobservable, and the resulting MDP $M$ governs the following transitions. Now, Papadimitriou and Tsitsiklis proved in 1987 that solving POMDPs is PSPACE-hard. The proof works by reducing QSAT to computing the value of a POMDP. Moreover, examining the reduction shows that the POMDP they construct is exactly of the form $\hat{M}$! Specifically, the random unobservable transition in the beginning serves to select a clause in the formula of the given QSAT instance.

Thus, Papadimitriou and Tsitsiklis's result indeed shows that finding a Bayes optimal policy is intractable (under standard complexity theoretic assumptions). However, notably, their proof only works when exact Bayes optimality is required. This is because the universal quantifiers in the QSAT instance are replaced by random transitions in the MDP, which means that it might be possible to achieve high reward even for unsatisfiable formulas.

Now, Goldsmith, Lusena and Mundhenk proved in 2001 that even approximating the value of a POMDP is intractable. However, in their proof the POMDP is not of the form that interests us. More precisely, they start with a basic construction that is of the form $\hat{M}$, however they require a probability amplification that runs the basic POMDP many times, and each time it runs the unobservable part of the state is randomly reset.

So, AFAIK, it seems possible to have e.g. a polynomial-time approximation scheme that accepts a set of MDPs and $\xi$ as above and produces an $\epsilon$-approximation of $V^*$. Such a scheme would be possible to use to compute a nearly Bayes optimal policy (with $V_\pi \geq V^* - T\epsilon$). Does such a scheme exist? Or is there another theorem that forbids it?

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.