Introduction
Reinforcement learning (RL) theory has historically focused on episodic tasks—problems with well-defined start and end points, such as games or finite-horizon simulations. In these settings, policy updates occur naturally between episodes. However, many critical real-world applications, ranging from industrial robotics to web server management, operate as continuing systems. These systems lack natural resets, and frequent or erratic policy updates can lead to significant performance degradation and linear regret.
This paper introduces Lazy PSRL, a Bayesian RL algorithm designed for infinite-horizon, average-cost settings. By integrating a "lazy" update schedule with a novel smoothness condition, the authors provide a unified framework that achieves rate-optimal performance across both discrete and continuous control problems.
The Lazy PSRL Algorithm
Lazy PSRL extends the Posterior Sampling for Reinforcement Learning (PSRL) framework, often referred to as Thompson Sampling, to continuing systems. The algorithm maintains a posterior distribution over the unknown system parameters and samples a model to compute an optimal control policy.
The "Lazy" Update Rule
A core challenge in continuing systems is determining when to switch policies. Lazy PSRL addresses this by monitoring the information gain of the system. Instead of updating at every time step, the algorithm only re-plans when the uncertainty of the unknown parameters decreases significantly. Specifically, a re-planning phase is triggered only when the determinant of the precision matrix $V_t$ exceeds a predefined threshold. This "laziness" ensures that the system does not incur the costs of policy switching until it has acquired enough new information to justify a change.
Smoothly Parameterized Dynamics
To bridge the gap between different types of RL problems, the authors introduce a smoothness assumption. They posit that the system's dynamics change smoothly relative to its parameters, characterized by a smoothness map $M$. This abstraction allows a single mathematical proof to cover:
- Finite MDPs: Discrete-state problems where transitions are governed by probability matrices.
- Linear Quadratic Regulators (LQR): Continuous-state problems with linear dynamics and quadratic costs.
Theoretical Contributions
The paper provides a rigorous analysis of Lazy PSRL, establishing a Bayesian regret bound of $\tilde{O}(\sqrt{T})$. This is the theoretical "gold standard," indicating that the algorithm's performance gap relative to an optimal strategy grows only sublinearly at the best possible rate.
Key to this proof is the shift from complex "measure concentration" arguments to a more elegant variance concentration assumption. Furthermore, the authors demonstrate that the algorithm is robust to planning errors; the regret bound degrades gracefully (additively) if the underlying optimal control problem is solved with slight imprecision.
For systems where the state might become unbounded (e.g., a balancing robot), the authors propose a Stabilized version of the algorithm. This variant hands control to a robust, pre-defined stabilizing controller if the system state leaves a designated "safe" region, ensuring safety during the learning process.
Experimental Evaluation
The algorithm was evaluated on two distinct benchmarks:
- Queuing Control: A discrete-state problem involving the management of a 99-slot buffer. Lazy PSRL significantly outperformed the UCRL (Upper Confidence Reinforcement Learning) algorithm by exploiting the problem's underlying structure rather than learning every transition independently.
- Web Server Management: A continuous-state LQR problem based on Apache HTTP server models. Lazy PSRL achieved regret comparable to "optimistic" algorithms like OFULQ but with vastly superior computational efficiency. While optimistic methods often require solving complex non-convex optimizations at each step, Lazy PSRL only requires sampling from a posterior and solving a standard control problem.
Conclusion and Future Work
Lazy PSRL represents a significant step forward in making Bayesian RL practical for real-world, continuing systems. By balancing exploration with the stability of "lazy" updates, it achieves theoretical optimality and empirical efficiency.
However, challenges remain. The algorithm's performance depends on the ability to efficiently sample from the posterior and the availability of a known smoothness map. Future research may focus on extending these principles to high-dimensional, non-linear systems where neural networks serve as the function approximators, and where the smoothness properties are not known a priori.
Summary updated