Reinforcement learning typically treats each policy as a black box, but many operational problems have structure: the trajectory generated under one policy may reveal how other policies would have performed. The authors formalize this as an information order over a parameterized policy class, writing πθ′ ⪯ πθ when data collected under πθ can estimate the long-run average cost of πθ′. This allows counterfactual inference to replace some direct exploration.
The paper introduces an epoch-based algorithm for infinite-horizon average-cost MDPs with continuous state and action spaces. For a d-dimensional policy class with information order width w, the algorithm attains regret of O~(H√(wdT/α)) relative to the optimal policy in the class, where H is a bias span bound and α is an information ratio. The width interpolates between full counterfactual feedback and unstructured policy learning, serving as a measure of effective exploration complexity.
The framework is instantiated in lost-sales inventory systems with positive lead times, dual-sourcing systems with 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.
The result is significant because it provides a principled way to quantify when and how much counterfactual information helps in sequential decision-making. By tying regret to the width of the information order, the work offers a bridge between structured models and general reinforcement learning, potentially guiding algorithm design for real-world systems where data is expensive and policies are related.