# Reinforcement Learning in MDPs with Information-Ordered Policies

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 5 Aug 2025.

## Placed in

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

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

- [Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?](https://mlsanity.com/paper/2601.20694/) (2026)
- [Offline-Online Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2604.11994/) (2026)
- [Towards Optimal Inventory Control under Censored Demand: A Biased Sample-Average Approximation Approach](https://mlsanity.com/paper/2609.39397/) (2026)

## Abstract (arXiv)

We propose an epoch-based reinforcement learning algorithm for infinite-horizon average-cost Markov decision processes (MDPs) that leverages a partial order over a policy class. In this structure, π' ≤ π if data collected under π can be used to estimate the performance of π', enabling counterfactual inference without additional environment interaction. Leveraging this partial order, we show that our algorithm achieves a regret bound of O(√w log(|Theta|) T), where w is the width of the partial order. Notably, the bound is independent of the state and action space sizes. We illustrate the applicability of these partial orders in many domains in operations research, including inventory control and queuing systems. For each, we apply our framework to that problem, yielding new theoretical guarantees and strong empirical results without imposing extra assumptions such as convexity in the inventory model or specialized arrival-rate structure in the queuing model.