Efficient reinforcement learning in parameterized models: discrete parameters

We consider reinforcement learning in a parameterized setup, where the controlled model is known to belong to a finite set of Markov Decision Processes (MDPs) under the discounted return criteria. We propose an on-line algorithm for learning in such parameterized models, called the Parameter Elimination (PEL) algorithm, and analyze its performance in terms of the the total mistake bound criterion, which upper-bounds the total number of suboptimal actions performed by the algorithm over the infinite time horizon. The proposed algorithm relies on Wald's Sequential Probability Ratio Test to eliminate unlikely parameters, and uses an optimistic policy for effective exploration. We establish that, with high probability, the total mistake bound for the algorithm is linear (up to a logarithmic term) in the cardinality |Θ| of the parameter set, independently of the cardinality of the state and action spaces. We further demonstrate that much better dependence |Θ| may be obtained for this algorithm, depending on the specific information structure of the problem.