A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits

2026-03-27 · Tor Lattimore arxiv

We adapt the analysis of policy gradient for continuous time $k$-armed stochastic bandits by Lattimore (2026) to the standard discrete time setup. As in continuous time, we prove that with learning rate $η= O(Δ_{\min}^2/(Δ_{\max} \log(n)))$ the regret is $O(k \log(k) \log(n) / η)$ where $n$ is the horizon and $Δ_{\min}$ and $Δ_{\max}$ are the minimum and maximum gaps.

📄 PDF Abstract BibTeX arXiv:2603.26547

Code (0)

등록된 구현이 없습니다.

A Short Note on Soft-max and Policy Gradients in Bandits Problems

2020-07-20 · Neil Walton

This is a short communication on a Lyapunov function argument for softmax in bandit problems. There are a number of excellent papers coming out using differential equations for policy gradient algorithms in reinforcement…

reinforcement-learning Reinforcement Learning (RL)

Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods

2023-10-04 · Sara Klein, Simon Weissmann, Leif Döring

Markov Decision Processes (MDPs) are a formal framework for modeling and solving sequential decision-making problems. In finite-time horizons such problems are relevant for instance for optimal stopping or specific suppl…

Decision Making Policy Gradient Methods Sequential Decision Making

Score-Aware Policy-Gradient Methods and Performance Guarantees using Local Lyapunov Conditions: Applications to Product-Form Stochastic Networks and Queueing Systems

2023-12-05 · Céline Comte, Matthieu Jonckheere, Jaron Sanders, Albert Senen-Cerda

In this paper, we introduce a policy-gradient method for model-based reinforcement learning (RL) that exploits a type of stationary distributions commonly obtained from Markov decision processes (MDPs) in stochastic netw…

Form Model-based Reinforcement Learning Policy Gradient Methods Reinforcement Learning (RL)

Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch

2021-11-04 · NeurIPS 2023 11 · Shangtong Zhang, Remi Tachet, Romain Laroche

In this paper, we establish the global optimality and convergence rate of an off-policy actor critic algorithm in the tabular setting without using density ratio to correct the discrepancy between the state distribution …

Policy Gradient Methods

Stochastic Gradient Descent with Adaptive Data

2024-10-02 · Ethan Che, Jing Dong, Xin T. Tong

Stochastic gradient descent (SGD) is a powerful optimization technique that is particularly useful in online learning scenarios. Its convergence analysis is relatively well understood under the assumption that the data s…