Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity

2020-06-06 · Zihan Zhang, Yuan Zhou, Xiangyang Ji

In this paper we consider the problem of learning an $\epsilon$-optimal policy for a discounted Markov Decision Process (MDP). Given an MDP with $S$ states, $A$ actions, the discount factor $\gamma \in (0,1)$, and an approximation threshold $\epsilon > 0$, we provide a model-free algorithm to learn an $\epsilon$-optimal policy with sample complexity $\tilde{O}(\frac{SA\ln(1/p)}{\epsilon^2(1-\gamma)^{5.5}})$ (where the notation $\tilde{O}(\cdot)$ hides poly-logarithmic factors of $S,A,1/(1-\gamma)$, and $1/\epsilon$) and success probability $(1-p)$. For small enough $\epsilon$, we show an improved algorithm with sample complexity $\tilde{O}(\frac{SA\ln(1/p)}{\epsilon^2(1-\gamma)^{3}})$. While the first bound improves upon all known model-free algorithms and model-based ones with tight dependence on $S$, our second algorithm beats all known sample complexity bounds and matches the information theoretic lower bound up to logarithmic factors.

📄 PDF Abstract BibTeX arXiv:2006.03864

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning (RL)

Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence

2026-07-22 · Runlong Zhou, Zihan Zhang, Maryam Fazel, Simon S. Du arxiv

We study horizon-free regret minimization for finite-horizon time-homogeneous tabular Markov decision processes with $S$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$. We propose a new …

Reinforcement Learning

Logarithmic Neyman Regret for Adaptive Estimation of the Average Treatment Effect

2024-11-21 · Ojash Neopane, Aaditya Ramdas, Aarti Singh

Estimation of the Average Treatment Effect (ATE) is a core problem in causal inference with strong connections to Off-Policy Evaluation in Reinforcement Learning. This paper considers the problem of adaptively selecting …

Causal Inference Off-policy evaluation

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

2023-05-24 · NeurIPS 2023 11 · Xiang Ji, Gen Li

A crucial problem in reinforcement learning is learning the optimal policy. We study this in tabular infinite-horizon discounted Markov decision processes under the online setting. The existing algorithms either fail to …

Settling the Sample Complexity of Model-Based Offline Reinforcement Learning

2022-04-11 · Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi 외

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 RL reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Provable Reset-free Reinforcement Learning by No-Regret Reduction

2023-01-06 · Hoai-An Nguyen, Ching-An Cheng

Reinforcement learning (RL) so far has limited real-world applications. One key challenge is that typical RL algorithms heavily rely on a reset mechanism to sample proper initial states; these reset mechanisms, in practi…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)