Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration

2026-04-19 · Donghwan Lee arxiv

Q-value iteration (Q-VI) is usually analyzed through the $γ$-contraction of the Bellman operator. This argument proves convergence to $Q^*$, but it gives only a coarse account of when the induced greedy policy becomes optimal. We study discounted Q-VI as a switching system and focus on the practically optimal solution set (POSS), the set of $Q$-functions whose tie-broken greedy policies are optimal. The main result shows that Q-VI reaches the optimal action class in finite time by entering an invariant tube around $\mathcal X_1=Q^*+\operatorname{span}(\mathbf 1)$, which is contained in the POSS. For every $\varepsilon>0$, the distance to $\mathcal X_1$ satisfies an exponential bound with rate $(\barρ+\varepsilon)^k$, where $\barρ$ is the joint spectral radius of the projected switching family restricted to directions transverse to $\mathcal X_1$. When $\barρ<γ$, this transverse convergence is faster than the classical contraction rate. The analysis separates fast policy identification from the subsequent convergence to $Q^*$, which may still be governed by the all-ones mode. We also give spectral and graph-theoretic conditions under which the strict inequality $\barρ<γ$ holds or fails.

📄 PDF Abstract BibTeX arXiv:2604.17457

Code (0)

등록된 구현이 없습니다.

Faster Fixed-Point Methods for Multichain MDPs

2025-06-26 · Matthew Zurek, Yudong Chen

We study value-iteration (VI) algorithms for solving general (a.k.a. multichain) Markov decision processes (MDPs) under the average-reward criterion, a fundamental but theoretically challenging setting. Beyond the diffic…

Multi-Bellman operator for convergence of $Q$-learning with linear function approximation

2023-09-28 · Diogo S. Carvalho, Pedro A. Santos, Francisco S. Melo

We study the convergence of $Q$-learning with linear function approximation. Our key contribution is the introduction of a novel multi-Bellman operator that extends the traditional Bellman operator. By exploring the prop…

Q-Learning

Successive Over Relaxation Q-Learning

2019-03-09 · Chandramouli Kamanchi, Raghuram Bharadwaj Diddigi, Shalabh Bhatnagar

In a discounted reward Markov Decision Process (MDP), the objective is to find the optimal value function, i.e., the value function corresponding to an optimal policy. This problem reduces to solving a functional equatio…

Q-Learning Reinforcement Learning Reinforcement Learning (RL)

The Uncertainty Bellman Equation and Exploration

2017-09-15 · ICML 2018 7 · Brendan O'Donoghue, Ian Osband, Remi Munos, Volodymyr Mnih

We consider the exploration/exploitation problem in reinforcement learning. For exploitation, it is well known that the Bellman equation connects the value at any time-step to the expected value at subsequent time-steps.…

Reinforcement Learning

Behavior-Induced Mirror-Prox Temporal-Difference Learning for Faster Off-Policy Prediction

2026-05-16 · Xingguo Chen, Yuchen Shen, Shangdong Yang, Chao Li 외 arxiv

Gradient temporal-difference methods provide stable off-policy prediction with linear function approximation, but their practical performance is strongly affected by the geometry induced by the auxiliary-variable metric.…