# An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 5 of its 24 references that are in the map.
- First posted on arXiv 17 Nov 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Approachability, Regret and Calibration; implications and equivalences](https://mlsanity.com/paper/1301.2663/) (2013)
- [Approachability in Stackelberg Stochastic Games with Vector Costs](https://mlsanity.com/paper/1411.0728/) (2014)
- [Singularly perturbed linear programs and Markov decision processes](https://mlsanity.com/paper/1611.07388/) (2016)
- [Robust Correlated Equilibrium: Definition and Computation](https://mlsanity.com/paper/2311.17592/) (2023)

## Abstract (arXiv)

We propose a reinforcement learning (RL) framework for multi-objective decision-making, where the agent seeks to optimize a vector of rewards rather than a single scalar value. The objective is to ensure that the time-averaged reward vector converges asymptotically to a predefined target set. Since standard RL algorithms operate on scalar rewards, we introduce a dynamic scalarization mechanism guided by Blackwell's Approachability Theorem. This theorem enables adaptive updates of the scalarization vector to guarantee convergence toward the target set. Assuming ergodicity, the Markov chain induced by the learned policies admits a stationary distribution, ensuring all states recur with finite return times. Our algorithm exploits this property by defining an inner loop that applies a policy gradient method (with baseline) between successive visits to a designated recurrent state, enforcing Blackwell's condition at each iteration. An outer loop then updates the scalarization vector after each recurrence. We establish theoretical convergence of the long-run average reward vector to the target set and validate the approach through a numerical example.