Achieving Constant Regret in Linear Markov Decision Processes

• URL: http://arxiv.org/abs/2404.10745v2
• Date: Thu, 12 Dec 2024 17:42:52 GMT
• Title: Achieving Constant Regret in Linear Markov Decision Processes
• Authors: Weitong Zhang, Zhiyuan Fan, Jiafan He, Quanquan Gu,
• Abstract summary: We introduce an algorithm, Cert-LSVI-UCB, for misspecified linear Markov decision processes (MDPs) We show that Cert-LSVI-UCB has a cumulative regret of $tildemathcalO(d3H5/Delta)$ with high probability, provided that the misspecification level $zeta$ is below $tildemathcalO(Delta / (sqrtdH2))$.
• Score: 57.34287648914407
• License:
• Abstract: We study the constant regret guarantees in reinforcement learning (RL). Our objective is to design an algorithm that incurs only finite regret over infinite episodes with high probability. We introduce an algorithm, Cert-LSVI-UCB, for misspecified linear Markov decision processes (MDPs) where both the transition kernel and the reward function can be approximated by some linear function up to misspecification level $\zeta$. At the core of Cert-LSVI-UCB is an innovative \method, which facilitates a fine-grained concentration analysis for multi-phase value-targeted regression, enabling us to establish an instance-dependent regret bound that is constant w.r.t. the number of episodes. Specifically, we demonstrate that for a linear MDP characterized by a minimal suboptimality gap $\Delta$, Cert-LSVI-UCB has a cumulative regret of $\tilde{\mathcal{O}}(d^3H^5/\Delta)$ with high probability, provided that the misspecification level $\zeta$ is below $\tilde{\mathcal{O}}(\Delta / (\sqrt{d}H^2))$. Here $d$ is the dimension of the feature space and $H$ is the horizon. Remarkably, this regret bound is independent of the number of episodes $K$. To the best of our knowledge, Cert-LSVI-UCB is the first algorithm to achieve a constant, instance-dependent, high-probability regret bound in RL with linear function approximation without relying on prior distribution assumptions.

Related papers

• Provably Efficient CVaR RL in Low-rank MDPs [58.58570425202862]
  We study risk-sensitive Reinforcement Learning (RL) We propose a novel Upper Confidence Bound (UCB) bonus-driven algorithm to balance interplay between exploration, exploitation, and representation learning in CVaR RL. We prove that our algorithm achieves a sample complexity of $epsilon$-optimal CVaR, where $H$ is the length of each episode, $A$ is the capacity of action space, and $d$ is the dimension of representations.
  arXiv  Detail & Related papers  (2023-11-20T17:44:40Z)
• Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback [30.23951525723659]
  We study the low-rank MDPs with adversarially changed losses in the full-information feedback setting. We propose a policy optimization-based algorithm POLO, and we prove that it attains the $widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee.
  arXiv  Detail & Related papers  (2023-11-14T03:12:43Z)
• Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning [0.0]
  We study the problem of episodic reinforcement learning in continuous state-action spaces with unknown rewards and transitions. We propose an algorithm, BEF-RLSVI, that uses penalized maximum likelihood estimators to learn the unknown parameters.
  arXiv  Detail & Related papers  (2022-10-05T08:26:49Z)
• Provably Efficient Model-Free Constrained RL with Linear Function Approximation [4.060731229044571]
  We develop the first model-free, simulator-free algorithm that achieves a sublinear regret and a sublinear constraint violation even in large-scale systems. Our results are achieved via novel adaptations of the standard LSVI-UCB algorithms.
  arXiv  Detail & Related papers  (2022-06-23T17:54:31Z)
• Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation [25.60689712525918]
  We study reinforcement learning with linear function approximation where the transition probability and reward functions are linear. We propose a novel-efficient algorithm, LSVI-UCB$+$, which achieves an $widetildeO(HdsqrtT)$ regret bound where $H$ is the episode length, $d$ is the feature dimension, and $T$ is the number of steps.
  arXiv  Detail & Related papers  (2022-06-23T06:04:21Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
  We study episodic reinforcement learning in non-stationary linear (a.k.a. low-rank) Markov Decision Processes (MDPs) We propose OPT-WLSVI an optimistic model-free algorithm based on weighted least squares value which uses exponential weights to smoothly forget data that are far in the past. We show that our algorithm, when competing against the best policy at each time, achieves a regret that is upper bounded by $widetildemathcalO(d5/4H2 Delta1/4 K3/4)$ where $d$
  arXiv  Detail & Related papers  (2020-10-24T11:02:45Z)
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
  We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards. We empirically validate our approach in continuous MDPs with sparse rewards.
  arXiv  Detail & Related papers  (2020-04-12T12:23:46Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  We consider online learning for episodically constrained Markov decision processes (CMDPs) We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-02T05:02:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.