Settling the Sample Complexity of Online Reinforcement Learning
A central issue lying at the heart of online reinforcement learning (RL) is data efficiency. While a number of recent works achieved asymptotically minimal regret in online RL, the optimality of these results is only guaranteed in a ``large-sample'' regime, imposing enormous burn-in cost in order for their algorithms to operate optimally. How to achieve minimax-optimal regret without incurring any burn-in cost has been an open problem in RL theory. We settle this problem for the context of finite-horizon inhomogeneous Markov decision processes. Specifically, we prove that a modified version of Monotonic Value Propagation (MVP), a model-based algorithm proposed by \cite{zhang2020reinforcement}, achieves a regret on the order of (modulo log factors) \begin{equation*} \min\big\{ \sqrt{SAH^3K}, \,HK \big\}, \end{equation*} where $S$ is the number of states, $A$ is the number of actions, $H$ is the planning horizon, and $K$ is the total number of episodes. This regret matches the minimax lower bound for the entire range of sample size $K\geq 1$, essentially eliminating any burn-in requirement. It also translates to a PAC sample complexity (i.e., the number of episodes needed to yield $\varepsilon$-accuracy) of $\frac{SAH^3}{\varepsilon^2}$ up to log factor, which is minimax-optimal for the full $\varepsilon$-range. Further, we extend our theory to unveil the influences of problem-dependent quantities like the optimal value/cost and certain variances. The key technical innovation lies in the development of a new regret decomposition strategy and a novel analysis paradigm to decouple complicated statistical dependency -- a long-standing challenge facing the analysis of online RL in the sample-hungry regime.
Code (0)
등록된 구현이 없습니다.
Tasks
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning
Recently there is a surge of interest in understanding the horizon-dependence of the sample complexity in reinforcement learning (RL). Notably, for an RL environment with horizon length $H$, previous work have shown that…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning
The thriving field of multi-agent reinforcement learning (MARL) studies how a group of interacting agents make decisions autonomously in a shared dynamic environment. Existing theoretical studies in this area suffer from…
Multi-agent Reinforcement LearningSettling the Sample Complexity of Model-Based Offline Reinforcement Learning
This paper is concerned with offline reinforcement learning (RL), which learns using pre-collected data without further exploration. Effective offline RL would be able to accommodate distribution shift and limited data c…
Offline RLreinforcement-learningReinforcement LearningReinforcement Learning (RL)On annular short-time stability conditions for generalized Persidskii systems
This paper studies the trajectory behavior evaluation for generalized Persidskii systems with an essentially bounded input on a finite time interval. Also, the notions of annular settling and output annular settling for …
Enhanced sampled-data model predictive control via nonlinear lifting
This paper introduces a novel nonlinear model predictive control (NMPC) framework that incorporates a lifting technique to enhance control performance for nonlinear systems. While the lifting technique has been widely em…
Model Predictive Control