Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs

Philips George John, Arnab Bhattacharyya, Silviu Maniu, Dimitrios Myrisiotis, Zhenan Wu
11/16/2024
cs.LGcs.DS

No official code found. Best implementation: pseudonymousprocrastinator/efficient-low-regret-linear-mdp-rl (0 stars, last commit 2025-05-24).

Abstract

Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomial-time reinforcement learning algorithm (namely, LSVI-UCB) for the setting of linear Markov decision processes, and provided theoretical guarantees regarding its running time and regret. In real-world scenarios, however, the space usage of this algorithm can be prohibitive due to a utilized linear regression step. We propose and analyze two modifications of LSVI-UCB, which alternate periods of learning and not-learning, to reduce space and time usage while maintaining sublinear regret. We show experimentally, on synthetic data and real-world benchmarks, that our algorithms achieve low space usage and running time, while not significantly sacrificing regret.

View on arXivView PDF

Code Implementations(1)

pseudonymousprocrastinator/efficient-low-regret-linear-mdp-rlCommunity65%

Code for manuscript "Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs".

00Shell, PythonJun 19, 20241 years ago

Similar Papers

Online Reinforcement Learning in Markov Decision Process Using Linear Programming

88% match2023

Achieving Constant Regret in Linear Markov Decision Processes

87% match2024

Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback

87% match2026

Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time

87% match2023

Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs

86% match2024

What can online reinforcement learning with function approximation benefit from general coverage conditions?

85% match2023

Cite this paper

@article{john2024efficient,
  title  = {Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs},
  author = {Philips George John and Arnab Bhattacharyya and Silviu Maniu and Dimitrios Myrisiotis and Zhenan Wu},
  year   = {2024},
  eprint = {2411.10906},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2411.10906v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2411.10906.svg)](https://codeofpaper.com/paper/2411.10906)

Discussion