解决强化学习中状态观测延迟问题，提出最优算法。
Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning
- 结合状态扩展与置信上界方法处理延迟观测。
- 理论证明后悔界为 Õ(H√(D_max SAK))，达到最优。
- 适用于状态延迟场景，对算法设计有指导意义。
我们研究状态观测延迟的在线强化学习问题，即智能体在若干时间步后才观测到当前状态。提出一种融合状态增强与置信上界的方法。针对表格型马尔可夫决策过程（MDPs），推导出遗憾上界为 Õ(H √(D_max S A K))，其中 S、A 分别为状态和动作空间大小，H 为时间跨度，K 为回合数，D_max 为最大延迟。同时给出匹配的下界（对数因子外），证明该方法的最优性。分析框架将此问题视为更广泛一类MDP的特例，其转移动态可分解为已知与未知但结构化部分。建立了该抽象设定的一般性结果，可能具有独立研究价值。
原文摘要 · Abstract (English)
We study reinforcement learning with delayed state observation, where the agent observes the current state after some random number of time steps. We propose an algorithm that combines the augmentation method and the upper confidence bound approach. For tabular Markov decision processes (MDPs), we derive a regret bound of $\tilde{\mathcal{O}}(H \sqrt{D_{\max} SAK})$, where $S$ and $A$ are the cardinalities of the state and action spaces, $H$ is the time horizon, $K$ is the number of episodes, and $D_{\max}$ is the maximum length of the delay. We also provide a matching lower bound up to logarithmic factors, showing the optimality of our approach. Our analytical framework formulates this problem as a special case of a broader class of MDPs, where their transition dynamics decompose into a known component and an unknown but structured component. We establish general results for this abstract setting, which may be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。