Q-learning with Uniformly Bounded Variance
summary
Proposes a simple modification that subtracts a learned constant from the Bellman update so the linearization gets a rank‑one shift, moving the problematic eigenvalue and producing relative Q-learning with uniformly bounded variance even as gamma → 1. Uses stochastic‑approximation asymptotic covariance analysis to show standard tabular Q‑learning has infinite asymptotic variance for typical step sizes (gamma > 1/2) unless scaled by one-minus-gamma scaling, while the relative variant keeps finite covariance and empirical Bellman error stable at gamma = .999 and .9999.
AI-written summary · about
chapters (5)
- 0:00Start
- 5:39Q-learning and Galerkin Relaxation
- 14:18Convergence Rates of SA
- 24:55Application to Stochastic Shortest Path
- 28:37Conclusions & Future Work
related talks
33mTradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical Precision
45mPolicy Gradient: Optimal Estimation, Convergence, and Generalization beyond Cumulative Rewards
36mA Generalization Bound for Online Variational Inference
42m"Federated Reinforcement Learning: Statistical and Communication Trade-offs
01h 05mFoundations of RL
11mLinear Predictors in Reinforcement Learning: ...
15mMulti-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust Control
11mData Efficient Methods for Reinforcement Learning