基于策略偏序的强化学习算法，实现无额外交互的反事实推断。
Reinforcement Learning in MDPs with Information-Ordered Policies
- 利用策略间的偏序关系，通过已有数据评估其他策略性能。
- 理论证明算法在时间 T 内的累积遗憾为 $O(\sqrt{w \log(|Θ|) T})$。
- 适用于库存控制、排队系统等场景，无需凸性或特定到达率假设。
我们提出一种针对无限时域平均成本马尔可夫决策过程（MDP）的基于轮次的强化学习算法，该算法利用策略类上的部分序关系。当在策略 π 下收集的数据可用于估计策略 π' 的性能时，定义 π' ≤ π，从而实现无需额外环境交互的反事实推断。借助这一部分序，我们证明该算法的遗憾界为 $O(\sqrt{w \log(|Θ|) T})$，其中 $w$ 为部分序的宽度。值得注意的是，该界与状态空间和动作空间大小无关。我们在运筹学多个领域中展示了此类部分序的适用性，包括库存控制和排队系统。对每个问题应用该框架后，均获得了新的理论保证和强实证结果，且未引入如库存模型中的凸性或排队模型中的特殊到达率结构等额外假设。
原文摘要 · Abstract (English)
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, $π' \leq π$ 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(\sqrt{w \log(|Θ|) 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。