Abstract
Reinforcement learning (RL) theory has traditionally been dominated by Markov Decision Processes (MDPs), which assume that the current state provides all necessary information for future decision-making. However, real-world environments are often non-Markovian, non-ergodic, and partially observable. This paper, originally presented at IJCAI-17, establishes a theoretical foundation for Thompson Sampling (TS) in these complex, general environments. The authors demonstrate that Thompson Sampling is not only robust but achieves "objective" asymptotic optimality, overcoming the prior-belief biases that often hinder traditional Bayesian RL agents.
Introduction
In the realm of general reinforcement learning, Bayesian agents—such as the theoretical AIXI—face a significant challenge known as subjectivity. A standard Bayesian agent acts by maximizing the expected reward across all possible environments, weighted by a prior distribution. If the initial prior is poorly specified, the agent may fail to explore sufficiently, remaining trapped in sub-optimal behavior because it never receives enough evidence to correct its internal model.
This research investigates whether Thompson Sampling (also known as posterior sampling) can provide a more objective path to optimality. By sampling a single environment from the posterior and acting as if it were the true model, the TS agent introduces a form of "optimism" that forces deeper exploration than standard Bayesian averaging.
The Thompson Sampling Policy
The paper analyzes a specific implementation of the Thompson Sampling policy, denoted as $\pi_T$. The execution follows a cyclical three-step process:
- Sample: At the beginning of a decision period, the agent samples one environment ($\rho$) from its current posterior distribution.
- Act: The agent follows the optimal policy for that specific sampled environment for a duration defined as the effective horizon ($H_t$). This horizon is the time required to capture the majority of the future discounted reward.
- Update: After the horizon concludes, the agent updates its posterior distribution with the newly acquired data and repeats the process.
By committing to a sampled policy for the duration of the effective horizon, the agent ensures it explores the environment's dynamics deeply enough to yield meaningful updates to its beliefs.
Theoretical Insights: Breaking the Bayesian Bias
The core contribution of this work is the proof that Thompson Sampling is asymptotically optimal in mean for any countable class of stochastic environments. This finding is significant for several reasons:
Value-Scale Exploration
Unlike agents that attempt to learn every detail of their environment, the TS agent’s exploration is "reward-oriented." It focuses on learning the value of actions. This allows the agent to ignore irrelevant environmental complexities, focusing only on what is necessary to maximize long-term rewards.
Objective Optimality
The authors show that TS is "objectively" optimal. Regardless of how inaccurate the initial prior might be—provided it assigns a non-zero probability to the true environment—the agent will eventually converge to the optimal policy. This effectively mitigates the "prior bias" that plagues traditional Bayesian approaches.
Recoverability and Regret
To achieve sublinear regret—the gold standard for learning where the performance gap between the agent and the optimal policy vanishes over time—the environment must satisfy a "recoverability" condition. This means the agent must be able to eventually recover from the consequences of early exploratory mistakes. If an environment is recoverable, Thompson Sampling is guaranteed to achieve this vanishing regret.
Key Results
- Theorem 1: Establishes that Thompson Sampling is asymptotically optimal in mean for any countable class of stochastic environments, independent of the specific discount function used.
- Theorem 3 & Corollary 4: Demonstrates that under the recoverability assumption, Thompson Sampling achieves sublinear regret, proving that the agent's learning process is efficient in the long run.
Limitations and Challenges
While the theoretical results are robust, the authors identify several hurdles for practical implementation:
- Computational Complexity: The proofs assume a countable class of environments, which could theoretically include all computable programs. In practice, maintaining a posterior and sampling from such a vast space is computationally prohibitive.
- The "Trap" Problem: Asymptotic optimality is a limit result. It does not prevent an agent from falling into an irreversible "trap" early in the learning process. While the agent may act optimally given its current state in the limit, it may have already precluded the possibility of achieving the maximum possible total reward.
- Horizon and Discounting: In partially observable environments, standard geometric discounting often makes the recoverability assumption too restrictive. The authors suggest that moving toward "growing horizons" or alternative discount functions may be necessary for broader applicability.
Conclusion
This work provides a rigorous mathematical justification for the use of Thompson Sampling in general RL. By proving asymptotic optimality without the restrictive assumptions of ergodicity or Markovian dynamics, the authors elevate Thompson Sampling from a heuristic to a theoretically sound strategy for objective learning in complex worlds.
Summary updated