Thompson Sampling for Parameterized Markov Decision Processes with Uninformative Actions
This work provides theoretical guarantees for Bayesian learning in PMDPs, which is incremental as it extends Thompson sampling to handle uninformative actions in applications like queuing and inventory control.
The paper tackles the problem of learning in parameterized Markov Decision Processes with uninformative actions, achieving an asymptotically optimal expected regret bound of O(T^{-1}) using Thompson sampling.
We study parameterized MDPs (PMDPs) in which the key parameters of interest are unknown and must be learned using Bayesian inference. One key defining feature of such models is the presence of "uninformative" actions that provide no information about the unknown parameters. We contribute a set of assumptions for PMDPs under which Thompson sampling guarantees an asymptotically optimal expected regret bound of $O(T^{-1})$, which are easily verified for many classes of problems such as queuing, inventory control, and dynamic pricing.