Finite-Time Error Analysis of Soft Q-Learning: Switching System Approach

• URL: http://arxiv.org/abs/2403.06366v3
• Date: Thu, 5 Sep 2024 12:24:25 GMT
• Title: Finite-Time Error Analysis of Soft Q-Learning: Switching System Approach
• Authors: Narim Jeong, Donghwan Lee,
• Abstract summary: Soft Q-learning is a variation of Q-learning designed to solve entropy regularized Markov decision problems. This paper aims to offer a novel and unified finite-time, control-theoretic analysis of soft Q-learning algorithms.
• Score: 4.36117236405564
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Soft Q-learning is a variation of Q-learning designed to solve entropy regularized Markov decision problems where an agent aims to maximize the entropy regularized value function. Despite its empirical success, there have been limited theoretical studies of soft Q-learning to date. This paper aims to offer a novel and unified finite-time, control-theoretic analysis of soft Q-learning algorithms. We focus on two types of soft Q-learning algorithms: one utilizing the log-sum-exp operator and the other employing the Boltzmann operator. By using dynamical switching system models, we derive novel finite-time error bounds for both soft Q-learning algorithms. We hope that our analysis will deepen the current understanding of soft Q-learning by establishing connections with switching system models and may even pave the way for new frameworks in the finite-time analysis of other reinforcement learning algorithms.

Related papers

• 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)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Finite-Time Analysis of Minimax Q-Learning for Two-Player Zero-Sum Markov Games: Switching System Approach [3.5823366350053325]
  This paper investigates the finite-time analysis of a Q-learning algorithm applied to two-player zero-sum Markov games. We employ the switching system model of minimax Q-learning and the associated value iteration.
  arXiv  Detail & Related papers  (2023-06-09T06:39:37Z)
• On Robust Numerical Solver for ODE via Self-Attention Mechanism [82.95493796476767]
  We explore training efficient and robust AI-enhanced numerical solvers with a small data size by mitigating intrinsic noise disturbances. We first analyze the ability of the self-attention mechanism to regulate noise in supervised learning and then propose a simple-yet-effective numerical solver, Attr, which introduces an additive self-attention mechanism to the numerical solution of differential equations.
  arXiv  Detail & Related papers  (2023-02-05T01:39:21Z)
• Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic View [3.5823366350053325]
  This paper investigates new finite-time analysis of asynchronous Q-learning under Markovian observation models. In particular, we introduce a discrete-time time-varying switching system model of Q-learning with diminishing step-sizes. The proposed analysis brings in additional insights, covers different scenarios, and provides new simplified templates for analysis.
  arXiv  Detail & Related papers  (2022-07-25T14:15:55Z)
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs [50.75812033462294]
  We bridge the gap between practical success of Q-learning and pessimistic theoretical results. We present novel methods Q-Rex and Q-RexDaRe. We show that Q-Rex efficiently finds the optimal policy for linear MDPs.
  arXiv  Detail & Related papers  (2021-10-16T01:47:41Z)
• Finite-Time Analysis of Asynchronous Q-Learning with Discrete-Time Switching System Models [6.85316573653194]
  We prove that Q-learning with a constant step-size can be naturally formulated as discrete-time switched linear systems. It offers novel and intuitive insights on Q-learning mainly based on controloretic frameworks.
  arXiv  Detail & Related papers  (2021-02-17T05:32:07Z)
• Momentum Q-learning with Finite-Sample Convergence Guarantee [49.38471009162477]
  This paper analyzes a class of momentum-based Q-learning algorithms with finite-sample guarantee. We establish the convergence guarantee for MomentumQ with linear function approximations and Markovian sampling. We demonstrate through various experiments that the proposed MomentumQ outperforms other momentum-based Q-learning algorithms.
  arXiv  Detail & Related papers  (2020-07-30T12:27:03Z)
• Information Freshness-Aware Task Offloading in Air-Ground Integrated Edge Computing Systems [49.80033982995667]
  This paper studies the problem of information freshness-aware task offloading in an air-ground integrated multi-access edge computing system. A third-party real-time application service provider provides computing services to the subscribed mobile users (MUs) with the limited communication and computation resources from the InP. We derive a novel deep reinforcement learning (RL) scheme that adopts two separate double deep Q-networks for each MU to approximate the Q-factor and the post-decision Q-factor.
  arXiv  Detail & Related papers  (2020-07-15T21:32:43Z)
• Analysis of Q-learning with Adaptation and Momentum Restart for Gradient Descent [47.3692506462581]
  We first characterize the convergence rate for Q-AMSGrad, which is the Q-learning algorithm with AMSGrad update. To further improve the performance, we propose to incorporate the momentum restart scheme to Q-AMSGrad, resulting in the so-called Q-AMSGradR algorithm. Our experiments on a linear quadratic regulator problem show that the two proposed Q-learning algorithms outperform the vanilla Q-learning with SGD updates.
  arXiv  Detail & Related papers  (2020-07-15T01:11:43Z)
• Q-Learning with Differential Entropy of Q-Tables [4.221871357181261]
  We conjecture that the reduction in performance during prolonged training sessions of Q-learning is caused by a loss of information. We introduce Differential Entropy of Q-tables (DE-QT) as an external information loss detector to the Q-learning algorithm.
  arXiv  Detail & Related papers  (2020-06-26T04:37:10Z)

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.