Bayesian Optimal Control of Smoothly Parameterized Systems

We study Bayesian optimal control of a general class of smoothly parameterized Markov deci-sion problems (MDPs). We propose a lazy ver-sion of the so-called posterior sampling method, a method that goes back to Thompson and Strens, more recently studied by Osband, Russo and van Roy. While Osband et al. derived a bound on the (Bayesian) regret of this method for undis-counted total cost episodic, finite state and ac-tion problems, we consider the continuing, av-erage cost setting with no cardinality restric-tions on the state or action spaces. While in the episodic setting, it is natural to switch to a new policy at the episode-ends, in the continu-ing average cost framework we must introduce switching points explicitly and in a principled fashion, or the regret could grow linearly. Our lazy method introduces these switching points based on monitoring the uncertainty left about the unknown parameter. To develop a suitable and easy-to-compute uncertainty measure, we in-troduce a new “average local smoothness ” con-dition, which is shown to be satisfied in com-mon examples. Under this, and some additional mild conditions, we derive rate-optimal bounds on the regret of our algorithm. Our general ap-proach allows us to use a single algorithm and a single analysis for a wide range of problems, such as finite MDPs or linear quadratic regula-tion, both being instances of smoothly parame-terized MDPs. The effectiveness of our method is illustrated by means of a simulated example.