Safety
Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration
arXiv:2604.17457v2 Announce Type: replace-cross Abstract: Dynamic programming is one of the most fundamental methodologies for solving Markov decision problems. Among its many variants, Q-value iterat
arXiv:2604.17457v2 Announce Type: replace-cross Abstract: Dynamic programming is one of the most fundamental methodologies for solving Markov decision problems. Among its many variants, Q-value iteration (Q-VI) is particularly important due to its conceptual simplicity and its classical contraction-based convergence guarantee. Despite the central role of this contraction property, it does not fully reveal the geometric structure of the Q-VI trajectory. In particular, when one is interested not only in the final limit Q^* but also in when the induced greedy policy becomes effectively optimal, the standard contraction argument provides only a coarse characterization. To formalize this notion, we denote by mathcal X^* the set of Q-functions whose corresponding tie-broken greedy policies are optimal, referred to as the practically optimal solution set (POS). In this paper, we revisit discounted Q-VI through the lens of switching system theory and derive new geometric insights into its behavior. In particular, we show that although Q-VI does not reach Q^* in finite time in general, it identifies the optimal action class in finite time. Furthermore, we prove that the distance from the iterate to a particular subset of mathcal X^* decays exponentially at a rate governed by the joint spectral radius (JSR) of a restricted switching family. This rate can be strictly faster than the standard gamma rate when the restricted JSR is strictly smaller than gamma, while the convergence of the entire Q-function to Q^* can still be dominated by the slower gamma mode, where gamma denotes the discount factor. These results reveal a two-stage geometric behavior of Q-VI: a fast convergence toward mathcal X_1, followed by a slower convergence toward Q^* in general.
Related
- StructRL: Recovering Dynamic Programming Structure from Learning Dynamics in Distributional Reinforcement Learning
- CROP: Conservative Reward for Model-based Offline Policy Optimization
- On the Fundamental Limitations of Dual Static CVaR Decompositions in Markov Decision Processes
- Policy Testing in Markov Decision Processes
Source: arXiv cs.AI | 2026-04-22