Provably Efficient and Agile Randomized Q-Learning

• URL: http://arxiv.org/abs/2506.24005v1
• Date: Mon, 30 Jun 2025 16:08:29 GMT
• Title: Provably Efficient and Agile Randomized Q-Learning
• Authors: He Wang, Xingyu Xu, Yuejie Chi,
• Abstract summary: We propose a novel variant of Q-learning algorithm, refereed to as RandomizedQ, which integrates sampling-based exploration with agile, step-wise, policy updates.<n> Empirically, RandomizedQ exhibits outstanding performance compared to existing Q-learning variants with both bonus-based and Bayesian-based exploration on standard benchmarks.
• Score: 35.14581235983678
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While Bayesian-based exploration often demonstrates superior empirical performance compared to bonus-based methods in model-based reinforcement learning (RL), its theoretical understanding remains limited for model-free settings. Existing provable algorithms either suffer from computational intractability or rely on stage-wise policy updates which reduce responsiveness and slow down the learning process. In this paper, we propose a novel variant of Q-learning algorithm, refereed to as RandomizedQ, which integrates sampling-based exploration with agile, step-wise, policy updates, for episodic tabular RL. We establish an $\widetilde{O}(\sqrt{H^5SAT})$ regret bound, where $S$ is the number of states, $A$ is the number of actions, $H$ is the episode length, and $T$ is the total number of episodes. In addition, we present a logarithmic regret bound under a mild positive sub-optimality condition on the optimal Q-function. Empirically, RandomizedQ exhibits outstanding performance compared to existing Q-learning variants with both bonus-based and Bayesian-based exploration on standard benchmarks.

Related papers

• Q-learning with Posterior Sampling [3.598052011212994]
  We introduce Q-Learning with Posterior Sampling (P=KH), a simple Q-learning-based algorithm that uses Gaussian posteriors on Q-values for exploration.<n>We show that P achieves a regret bound of $tilde O(H2sqrtSAT)$, closely matching the known lower bound of $Omega(HsqrtSAT)$.<n>Our work provides several new technical insights into the core challenges in combining posterior sampling with dynamic programming and TD-learning-based RL algorithms.
  arXiv  Detail & Related papers  (2025-06-01T09:11:24Z)
• $β$-DQN: Improving Deep Q-Learning By Evolving the Behavior [41.13282452752521]
  $beta$-DQN is a simple and efficient exploration method that augments the standard DQN with a behavior function.<n>An adaptive meta-controller is designed to select an effective policy for each episode, enabling flexible and explainable exploration.<n>Experiments on both simple and challenging exploration domains show that $beta$-DQN outperforms existing baseline methods.
  arXiv  Detail & Related papers  (2025-01-01T18:12:18Z)
• Sublinear Regret for a Class of Continuous-Time Linear-Quadratic Reinforcement Learning Problems [10.404992912881601]
  We study reinforcement learning (RL) for a class of continuous-time linear-quadratic (LQ) control problems for diffusions.<n>We apply a model-free approach that relies neither on knowledge of model parameters nor on their estimations, and devise an RL algorithm to learn the optimal policy parameter directly.
  arXiv  Detail & Related papers  (2024-07-24T12:26:21Z)
• Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
  Transfer $Q*$ estimates the optimal value function for a target reward $r$ through a baseline model. Our approach significantly reduces the sub-optimality gap observed in prior SoTA methods.
  arXiv  Detail & Related papers  (2024-05-30T21:36:12Z)
• Stochastic Q-learning for Large Discrete Action Spaces [79.1700188160944]
  In complex environments with discrete action spaces, effective decision-making is critical in reinforcement learning (RL) We present value-based RL approaches which, as opposed to optimizing over the entire set of $n$ actions, only consider a variable set of actions, possibly as small as $mathcalO(log(n)$)$. The presented value-based RL methods include, among others, Q-learning, StochDQN, StochDDQN, all of which integrate this approach for both value-function updates and action selection.
  arXiv  Detail & Related papers  (2024-05-16T17:58:44Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  We show how to achieve minimax-optimal regret without incurring any burn-in cost.<n>We extend our theory to unveil the influences of problem-dependent quantities like the optimal value/cost and certain variances.
  arXiv  Detail & Related papers  (2023-07-25T15:42:11Z)
• Addressing Maximization Bias in Reinforcement Learning with Two-Sample Testing [0.0]
  Overestimation bias is a known threat to value-based reinforcement-learning algorithms. We propose a $T$-Estimator (TE) based on two-sample testing for the mean, that flexibly interpolates between over- and underestimation. We also introduce a generalization, termed $K$-Estimator (KE), that obeys the same bias and variance bounds as the TE.
  arXiv  Detail & Related papers  (2022-01-20T09:22:43Z)
• 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)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  This work sharpens the sample complexity of synchronous Q-learning to an order of $frac|mathcalS|| (1-gamma)4varepsilon2$ for any $0varepsilon 1$. Our finding unveils the effectiveness of vanilla Q-learning, which matches that of speedy Q-learning without requiring extra computation and storage.
  arXiv  Detail & Related papers  (2021-02-12T14:22:05Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  We provide the first non-asymptotic, finite-time analysis for double Q-learning. We show that both synchronous and asynchronous double Q-learning are guaranteed to converge to an $epsilon$-accurate neighborhood of the global optimum.
  arXiv  Detail & Related papers  (2020-09-29T18:48:21Z)
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret [44.374427255708135]
  We propose Exploration Enhanced Q-learning (EE-QL), a model-free algorithm for infinite-horizon average-reward Markov Decision Processes (MDPs) EE-QL assumes that an online concentrating approximation of the optimal average reward is available. This is the first model-free learning algorithm that achieves $O(sqrt T)$ regret without the ergodic assumption, and matches the lower bound in terms of $T$ except for logarithmic factors.
  arXiv  Detail & Related papers  (2020-06-08T05:09:32Z)

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.