The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective

2025-01-27 · Michael Muehlebach, Zhiyu He, Michael I. Jordan

We study the sample complexity of online reinforcement learning in the general setting of nonlinear dynamical systems with continuous state and action spaces. Our analysis accommodates a large class of dynamical systems ranging from a finite set of nonlinear candidate models to models with bounded and Lipschitz continuous dynamics, to systems that are parametrized by a compact and real-valued set of parameters. In the most general setting, our algorithm achieves a policy regret of $\mathcal{O}(N \epsilon^2 + \mathrm{ln}(m(\epsilon))/\epsilon^2)$, where $N$ is the time horizon, $\epsilon$ is a user-specified discretization width, and $m(\epsilon)$ measures the complexity of the function class under consideration via its packing number. In the special case where the dynamics are parametrized by a compact and real-valued set of parameters (such as neural networks, transformers, etc.), we prove a policy regret of $\mathcal{O}(\sqrt{N p})$, where $p$ denotes the number of parameters, recovering earlier sample-complexity results that were derived for linear time-invariant dynamical systems. While this article focuses on characterizing sample complexity, the proposed algorithms are likely to be useful in practice, due to their simplicity, their ability to incorporate prior knowledge, and their benign transient behavior.

📄 PDF Abstract BibTeX arXiv:2501.15910

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learning

2026-03-09 · Swetha Ganesh, Vaneet Aggarwal arxiv

While standard reinforcement learning optimizes a single reward signal, many applications require optimizing a nonlinear utility $f(J_1^π,\dots,J_M^π)$ over multiple objectives, where each $J_m^π$ denotes the expected di…

Reinforcement Learning

The Role of Coverage in Online Reinforcement Learning

2022-10-09 · Tengyang Xie, Dylan J. Foster, Yu Bai, Nan Jiang 외

Coverage conditions -- which assert that the data logging distribution adequately covers the state space -- play a fundamental role in determining the sample complexity of offline reinforcement learning. While such condi…

Efficient Exploration Offline RL reinforcement-learning Reinforcement Learning+1

Reinforcement Learning with Function Approximation: From Linear to Nonlinear

2023-02-20 · Jihao Long, Jiequn Han

Function approximation has been an indispensable component in modern reinforcement learning algorithms designed to tackle problems with large state spaces in high dimensions. This paper reviews recent results on error an…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data

2024-11-06 · Chengrui Qu, Laixi Shi, Kishan Panaganti, Pengcheng You 외

Online Reinforcement learning (RL) typically requires high-stakes online interaction data to learn a policy for a target task. This prompts interest in leveraging historical data to improve sample efficiency. The histori…

Reinforcement Learning (RL)Transfer Reinforcement Learning

Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach

2025-10-23 · Woohyeon Byeon, Giseung Park, Jongseong Chae, Amir Leshem 외 arxiv

In this paper, we propose a provably convergent and practical framework for multi-objective reinforcement learning with max-min criterion. From a game-theoretic perspective, we reformulate max-min multi-objective reinfor…