利用外生结构实现样本高效的强化学习

arXiv:2409.14557v5 发布类型：replace-cross 摘要：我们研究一类具有结构的马尔可夫决策过程，即 Exo-MDPs，其中状态空间被划分为外生和内生两个部分。外生状态以随机方式演化，且独立于智能体的动作；内生状态则根据两个状态组成部分和动作确定性地演化。Exo-MDPs 涵盖了许多运筹学场景，包括库存控制、资源管理和共享出行。我们的第一项贡献是结构性的：我们建立了离散 MDPs、Exo-MDPs 和离散线性混合 MDPs 之间的表示等价性。我们的第二项贡献是统计性的：当有效维度 r 相对于内生状态空间和动作空间较小时，我们刻画了在 Exo-MDPs 中进行学习的极小极大遗憾。当外生状态不可观测时，我们证明，在长度为 H 的 K 个回合上，遗憾的上界和下界相匹配，均为 $\Theta(Hr \sqrt{K})$，其中 r 是 Exo-MDP 的有效维度。当外生状态可观测时，极小极大遗憾降至 $\Theta(H\sqrt{ r K})$，表明观测外生状态可带来 $\Theta(\sqrt{r})$ 的统计差距。这些结果表明，Exo-MDPs 将样本复杂度与动作空间和内生状态空间解耦。我们通过库存控制和资源分配实验验证了这些结论。