Thompson Sampling for Infinite-Horizon Discounted Decision Processes
Authors: Daniel Adelman, Cagla Keceli, Alba V. Olivares-Nadal
Abstract
This paper develops a framework for learning in discounted infinite-horizon Markov decision processes (MDPs) with Borel state and action spaces, whose rewards and transitions depend on an unknown parameter.To analyze sampling-based adaptive learning algorithms in this setting, we introduce a canonical probability space that explicitly incorporates sampled parameters into the history of the process. As a performance criterion, we adopt the per-period suboptimality gap used in discounted-MDP regret analysis and specialize it to our parametrized Bayesian setting. Since this quantity captures the remaining loss in future performance from the current period onward, we refer to it as residual regret. We use the expected residual regret to connect discounted-MDP regret analysis with asymptotic discount optimality from adaptive control and the temporal-difference error perspective from reinforcement learning. We then focus on Thompson sampling (TS) in discounted infinite-horizon MDPs. Under assumptions that extend those used in prior work on finite state and action spaces to the Borel setting, we show that the expected residual regret for TS converges to zero exponentially fast. We further show that, under mild conditions ensuring the existence of the relevant limits, the ample-path residual regret converges to zero almost surely and TS achieves complete learning.
A Tree Markov Decision Problem (T-MDP) is a finite-horizon MDP with a starting state s1, in which every state is reachable from s1 through exactly one state-action trajectory. T-MDPs arise naturally as abstractions of decision making in sequential games with perfect recall, against stationary opponents. We consider the problem of on-line learning in T-MDPs, both in the PAC and the regret-minimisation regimes. We show that well-known bandit algorithms -- \textsc{Lucb} and \textsc{Ucb} -- can be applied on T-MDPs by treating each policy as an arm. The apparent technical challenge in this approach is that the number of policies is exponential in the number of states. Our main innovation is in the design of confidence bounds based on data shared by the policies, so that the bandit algorithms can yet be implemented with polynomial memory and per-step computation. We obtain instance-dependent upper bounds on sample complexity and regret that sum a ``gap term'' from every terminal state, rather than every policy. Empirically, our algorithms consistently outperform available alternatives on a suite of hidden-information games.
We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our analysis applies as long as the latent arm processes are independent and each arm evolves only when played. For stochastic bandits with best arm defined via mean reward, this confirms a conjecture of Guha and Munagala from 2014, where the factor 2 is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.
We analyze the Bayesian regret of the Gaussian process posterior sampling reinforcement learning (GP-PSRL) algorithm. Posterior sampling is a heuristic for decision-making under uncertainty that has been used to develop successful algorithms for a variety of continuous control problems. However, theoretical work on GP-PSRL is limited. All known regret bounds either have a sub-optimal growth rate, require strong smoothness assumptions, or fail to properly account for the fact that the set of possible system states is unbounded. Through a recursive application of the Borell-Tsirelson-Ibragimov-Sudakov inequality, we show that, with high probability, the states actually visited by the algorithm are contained within a ball of near-constant radius. We then use the chaining method to control the regret suffered by GP-PSRL under weak smoothness conditions. Our main result is a Bayesian regret bound of the order O(HγTT), where H is the horizon, T is the number of time steps and γT is the expected information gain. With this result, we resolve the limitations with prior theoretical work on PSRL, and provide the theoretical foundation and tools for analyzing PSRL in complex settings.