On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes

• URL: http://arxiv.org/abs/2408.16262v1
• Date: Thu, 29 Aug 2024 04:57:44 GMT
• Title: On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes
• Authors: Yi Wan, Huizhen Yu, Richard S. Sutton,
• Abstract summary: This paper analyzes reinforcement learning (RL) algorithms for Markov decision processes (MDPs) under the average-reward criterion. We focus on Q-learning algorithms based on relative value (RVI), which are model-free sets of the iteration RVI method for weakly communicating MDPs.
• Score: 11.868402302316131
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper analyzes reinforcement learning (RL) algorithms for Markov decision processes (MDPs) under the average-reward criterion. We focus on Q-learning algorithms based on relative value iteration (RVI), which are model-free stochastic analogues of the classical RVI method for average-reward MDPs. These algorithms have low per-iteration complexity, making them well-suited for large state space problems. We extend the almost-sure convergence analysis of RVI Q-learning algorithms developed by Abounadi, Bertsekas, and Borkar (2001) from unichain to weakly communicating MDPs. This extension is important both practically and theoretically: weakly communicating MDPs cover a much broader range of applications compared to unichain MDPs, and their optimality equations have a richer solution structure (with multiple degrees of freedom), introducing additional complexity in proving algorithmic convergence. We also characterize the sets to which RVI Q-learning algorithms converge, showing that they are compact, connected, potentially nonconvex, and comprised of solutions to the average-reward optimality equation, with exactly one less degree of freedom than the general solution set of this equation. Furthermore, we extend our analysis to two RVI-based hierarchical average-reward RL algorithms using the options framework, proving their almost-sure convergence and characterizing their sets of convergence under the assumption that the underlying semi-Markov decision process is weakly communicating.

Related papers

• Q-learning for Quantile MDPs: A Decomposition, Performance, and Convergence Analysis [30.713243690224207]
  In Markov decision processes (MDPs), quantile risk measures such as Value-at-Risk are a standard metric for modeling RL agents' preferences for certain outcomes. This paper proposes a new Q-learning algorithm for quantile optimization in MDPs with strong convergence and performance guarantees.
  arXiv  Detail & Related papers  (2024-10-31T16:53:20Z)
• Asynchronous Stochastic Approximation and Average-Reward Reinforcement Learning [11.868402302316131]
  We extend Borkar and Meyn's stability proof method to accommodate more general noise conditions. We establish the convergence of an asynchronous SA analogue of Schweitzer's classical relative value algorithm, RVI Q-learning. We introduce new monotonicity conditions for estimating the optimal reward rate in RVI Q-learning.
  arXiv  Detail & Related papers  (2024-09-05T21:23:51Z)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS) For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. We extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.
  arXiv  Detail & Related papers  (2024-04-30T06:48:56Z)
• Multi-Timescale Ensemble Q-learning for Markov Decision Process Policy Optimization [21.30645601474163]
  Original Q-learning suffers from performance and complexity challenges across very large networks. New model-free ensemble reinforcement learning algorithm which adapts the classical Q-learning is proposed to handle these challenges. Numerical results show that the proposed algorithm can achieve up to 55% less average policy error with up to 50% less runtime complexity.
  arXiv  Detail & Related papers  (2024-02-08T08:08:23Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• Model-Free Robust Average-Reward Reinforcement Learning [25.125481838479256]
  We focus on the robust average-reward MDPs under the model-free iteration setting. We design two model-free algorithms, robust relative value (RVI) TD and robust RVI Q-learning, and theoretically prove their convergence to the optimal solution.
  arXiv  Detail & Related papers  (2023-05-17T18:19:23Z)
• On Practical Robust Reinforcement Learning: Practical Uncertainty Set and Double-Agent Algorithm [11.748284119769039]
  Robust reinforcement learning (RRL) aims at seeking a robust policy to optimize the worst case performance over an uncertainty set of Markov decision processes (MDPs)
  arXiv  Detail & Related papers  (2023-05-11T08:52:09Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  Bilevel optimization (BO) has arisen as a powerful tool for solving many modern machine learning problems. Existing gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations. We propose a novel BO algorithm, which adopts Evolution Strategies (ES) based method to approximate the response Jacobian matrix in the hypergradient of BO.
  arXiv  Detail & Related papers  (2021-10-13T19:36:50Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.