Reinforcement Learning in MDPs with Information-Ordered Policies

arXiv:2508.03904v2 Announce Type: replace-cross 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'} \preceq \pi_\theta$ when data collected under $\pi_\theta$ can be used to estimate the long-run average cost of $\pi_{\theta'}$. 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 $\widetilde 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.

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'} \preceq \pi_\theta$ when data collected under $\pi_\theta$ can be used to estimate the long-run average cost of $\pi_{\theta'}$. 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 $\widetilde 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.

Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC)

arXiv:2508.03904 [stat.ML]

(or arXiv:2508.03904v2 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2508.03904 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Reinforcement Learning in MDPs with Information-Ordered Policies

Subiecte conexe