# Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2019.

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

- [The Importance of Non-Markovianity in Maximum State Entropy Exploration](https://mlsanity.com/paper/2202.03060/) (2022)
- [Fast Rates for Maximum Entropy Exploration](https://mlsanity.com/paper/2303.08059/) (2023)
- [Challenging Common Assumptions in Convex Reinforcement Learning](https://mlsanity.com/paper/2202.01511/) (2022)
- [Probabilistic Inference in Reinforcement Learning Done Right](https://mlsanity.com/paper/2311.13294/) (2023)
- [On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks](https://mlsanity.com/paper/2401.14811/) (2024)
- [Active Coverage for PAC Reinforcement Learning](https://mlsanity.com/paper/2306.13601/) (2023)
- [Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.16600/) (2024)
- [TAB-Fields: A Maximum Entropy Framework for Mission-Aware Adversarial Planning](https://mlsanity.com/paper/2412.02570/) (2024)

## Abstract (arXiv)

We consider an agent who is involved in a Markov decision process and receives a vector of outcomes every round. Her objective is to maximize a global concave reward function on the average vectorial outcome. The problem models applications such as multi-objective optimization, maximum entropy exploration, and constrained optimization in Markovian environments. In our general setting where a stationary policy could have multiple recurrent classes, the agent faces a subtle yet consequential trade-off in alternating among different actions for balancing the vectorial outcomes. In particular, stationary policies are in general sub-optimal. We propose a no-regret algorithm based on online convex optimization (OCO) tools (Agrawal and Devanur 2014) and UCRL2 (Jaksch et al. 2010). Importantly, we introduce a novel gradient threshold procedure, which carefully controls the switches among actions to handle the subtle trade-off. By delaying the gradient updates, our procedure produces a non-stationary policy that diversifies the outcomes for optimizing the objective. The procedure is compatible with a variety of OCO tools.