通过结构化建模提升强化学习采样效率,适用于库存与资源管理场景。
Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning
- 将状态分为外生与内生部分,利用其结构降低学习难度。
- 外生状态不可见时,最小后悔值为 Θ(Hr√K),可见时降至 Θ(H√(rK))。
- 特别适合动作空间大、状态复杂但结构清晰的工业优化问题。
我们研究一类称为Exo-MDP的结构化马尔可夫决策过程,其中状态空间被划分为外生和内生部分。外生状态独立于智能体行为随机演化,而内生状态则根据两者及动作确定性演化。该模型涵盖库存控制、资源管理、网约车等应用场景。首个贡献是理论上的:建立了离散MDP、Exo-MDP与离散线性混合MDP之间的表示等价性。第二个贡献是统计性质:当有效维度 r 相对于内生状态与动作空间较小时,我们刻画了学习过程中的极小最大后悔值。当外生状态不可观测时,最优上下界为 Θ(Hr√K),在 K 轮、每轮长度为 H 的环境中;当外生状态可观测时,后悔值降为 Θ(H√(rK)),揭示出可观测性带来的 Θ(√r) 统计优势。这些结果表明,在Exo-MDP中,样本复杂度可与动作空间和内生状态空间解耦。实验验证了在库存控制与资源分配任务中的有效性。
原文摘要 · Abstract (English)
We study a structured class of Markov Decision Processes, known as Exo-MDPs, in which the state space is partitioned into exogenous and endogenous components. Exogenous states evolve stochastically, independent of the agent's actions, while endogenous states evolve deterministically based on both state components and actions. Exo-MDPs capture many operations research settings, including inventory control, resource management, and ride-sharing. Our first contribution is structural: we establish a representational equivalence between discrete MDPs, Exo-MDPs, and discrete linear mixture MDPs. Our second contribution is statistical. We characterize the minimax regret of learning in Exo-MDPs when the effective dimension r is small relative to the endogenous state and action spaces. When the exogenous states are unobserved, we prove matching upper and lower regret bounds of order $Θ(Hr \sqrt{K})$ over $K$ episodes of horizon $H$, where $r$ is the effective dimension of the Exo-MDP. When exogenous states are observed, the minimax regret improves to $Θ(H\sqrt{ r K})$, revealing a $Θ(\sqrt{r})$ statistical gap due to observation of the exogenous states. These results show that Exo-MDPs decouple sample complexity from action space and endogenous state space. We validate these insights with experiments on inventory control and resource allocation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。