Near-Optimal Randomized Exploration for Tabular Markov Decision Processes

2021-02-19 · Zhihan Xiong, Ruoqi Shen, Qiwen Cui, Maryam Fazel, Simon S. Du

We study algorithms using randomized value functions for exploration in reinforcement learning. This type of algorithms enjoys appealing empirical performance. We show that when we use 1) a single random seed in each episode, and 2) a Bernstein-type magnitude of noise, we obtain a worst-case $\widetilde{O}\left(H\sqrt{SAT}\right)$ regret bound for episodic time-inhomogeneous Markov Decision Process where $S$ is the size of state space, $A$ is the size of action space, $H$ is the planning horizon and $T$ is the number of interactions. This bound polynomially improves all existing bounds for algorithms based on randomized value functions, and for the first time, matches the $\Omega\left(H\sqrt{SAT}\right)$ lower bound up to logarithmic factors. Our result highlights that randomized exploration can be near-optimal, which was previously achieved only by optimistic algorithms. To achieve the desired result, we develop 1) a new clipping operation to ensure both the probability of being optimistic and the probability of being pessimistic are lower bounded by a constant, and 2) a new recursive formula for the absolute value of estimation errors to analyze the regret.

📄 PDF Abstract BibTeX arXiv:2102.09703

Code (0)

등록된 구현이 없습니다.

Worst-Case Regret Bounds for Exploration via Randomized Value Functions

2019-06-07 · NeurIPS 2019 12 · Daniel Russo

This paper studies a recent proposal to use randomized value functions to drive exploration in reinforcement learning. These randomized value functions are generated by injecting random noise into the training data, maki…

Efficient Exploration reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes

2026-05-05 · Cyrille Kone, Kevin Jamieson arxiv

We study the $(\varepsilon, δ)$-PAC policy identification problem in finite-horizon episodic Markov Decision Processes. Existing approaches provide finite-time guarantees for approximate settings ($\varepsilon>0$) but su…

No-regret Exploration in Contextual Reinforcement Learning

2019-03-14 · Aditya Modi, Ambuj Tewari

We consider the recently proposed reinforcement learning (RL) framework of Contextual Markov Decision Processes (CMDP), where the agent interacts with a (potentially adversarial) sequence of episodic tabular MDPs. In add…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Model-free Posterior Sampling via Learning Rate Randomization

2023-10-27 · NeurIPS 2023 11

In this paper, we introduce Randomized Q-learning (RandQL), a novel randomized model-free algorithm for regret minimization in episodic Markov Decision Processes (MDPs). To the best of our knowledge, RandQL is the first …

model Q-Learning

Frequentist Regret Bounds for Randomized Least-Squares Value Iteration

2019-11-01 · Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta 외

We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning (RL). When the state space is large or continuous, traditional tabular approaches are unfeasible and some form of function approxi…

Reinforcement Learning Reinforcement Learning (RL)