# MDP Geometry, Normalization and Reward Balancing Solvers

arXiv: https://arxiv.org/abs/2407.06712 · HTML: https://mlsanity.com/paper/2407.06712/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 9 Jul 2024.

## Builds on (most cited first, 10 of 10)

- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [The Value-Improvement Path: Towards Better Representations for Reinforcement Learning](https://mlsanity.com/paper/2006.02243/) (2020)
- [A Geometric Perspective on Optimal Representations for Reinforcement Learning](https://mlsanity.com/paper/1901.11530/) (2019)
- [The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond](https://mlsanity.com/paper/2305.10697/) (2023)
- [The Value Function Polytope in Reinforcement Learning](https://mlsanity.com/paper/1901.11524/) (2019)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup](https://mlsanity.com/paper/2012.15511/) (2020)
- [Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes](https://mlsanity.com/paper/2002.00874/) (2020)
- [The Value Iteration Algorithm is Not Strongly Polynomial for Discounted Dynamic Programming](https://mlsanity.com/paper/1312.6832/) (2013)

## Built on by (most cited first, 3 of 3)

- [Geometric Re-Analysis of Classical MDP Solving Algorithms](https://mlsanity.com/paper/2503.04203/) (2025)
- [Revisiting Value Iteration: Unified Analysis of Discounted and Average-Reward Cases](https://mlsanity.com/paper/2510.23914/) (2025)
- [On Reward-Balancing Methods for Reinforcement Learning](https://mlsanity.com/paper/2604.20433/) (2026)

## Abstract (arXiv)

We present a new geometric interpretation of Markov Decision Processes (MDPs) with a natural normalization procedure that allows us to adjust the value function at each state without altering the advantage of any action with respect to any policy. This advantage-preserving transformation of the MDP motivates a class of algorithms which we call Reward Balancing, which solve MDPs by iterating through these transformations, until an approximately optimal policy can be trivially found. We provide a convergence analysis of several algorithms in this class, in particular showing that for MDPs for unknown transition probabilities we can improve upon state-of-the-art sample complexity results.