Reinforcement Learning in MDPs with Information-Ordered Policies

Abstract

Many operational Markov decision processes provide structured information where a trajectory generated under one policy may also reveal how other policies would have performed. We formalize this through an information order over a parameterized policy class, writing ${\pi }_{{\theta }^{\prime }}⪯{\pi }_{\theta }$ when data collected under ${\pi }_{\theta }$ can be used to estimate the long-run average cost of ${\pi }_{{\theta }^{\prime }}$. We develop an epoch-based reinforcement learning algorithm for infinite-horizon average-cost MDPs with continuous state and action spaces that exploits this order through counterfactual inference. For a $d$-dimensional policy class whose information order has width $w$, the algorithm achieves $\tilde{O}(H\sqrt{wdT/\alpha })$ regret relative to the optimal policy in the class, where $H$ is a bias span upper bound and $\alpha$ denotes an "information ratio". Thus, the width captures the effective exploration complexity of the problem, interpolating between full counterfactual feedback and unstructured policy learning. We instantiate the framework in lost-sales inventory systems with positive lead times, dual-sourcing systems governed by dual-index policies, and queues with state-dependent service rates. These applications yield new regret guarantees without requiring global convexity of the average-cost function or specialized arrival-rate structure. Numerical experiments show that exploiting the information order substantially improves learning performance over existing general-purpose and problem-specific benchmarks.

arXiv comment94 pages, 3 figures