提出新算法，解决上下文相关随机最短路径问题的后悔边界挑战。
Regret Guarantees for Linear Contextual Stochastic Shortest Path
- 基于线性上下文建模动态，设计自适应学习策略。
- 实现 $\widetilde{O}(K^{2/3} d^{2/3} |S| |A|^{1/3} B_\star^2 T_\star)$ 的后悔上界。
- 适用于连续上下文空间，确保每轮快速终止，适合强化学习研究者。
我们定义了线性上下文随机最短路径（CSSP）问题：每轮开始时，学习者观测到一个对抗性选择的上下文，该上下文通过固定但未知的线性函数决定马尔可夫决策过程（MDP）。学习者的任务是在不知晓转移动态、损失函数或上下文到MDP映射的情况下，以最小期望累积损失到达指定目标状态。本文提出LR-CSSP算法，其后悔上界为 $\widetilde{O}(K^{2/3} d^{2/3} |S| |A|^{1/3} B_\star^2 T_\star \log(1/δ))$，其中 $K$ 为轮次数，$d$ 为上下文维度，$|S|$、$|A|$ 分别为状态与动作集大小，$B_\star$ 为最优累积损失上界，$T_\star$ 为最优策略到达目标的期望时间（未知）。当所有代价大于 $\ell_{\min}$ 时，后悔为 $\widetilde{O}(\sqrt{K \cdot d^2 |S|^3 |A| B_\star^3 \log(1/δ)/\ell_{\min}})$。与有限时域上下文MDP不同，此处知识不足可能延长甚至导致非终止的轮次。分析表明，LR-CSSP能有效处理连续上下文空间，并保证所有轮次在合理步数内终止。
原文摘要 · Abstract (English)
We define the problem of linear Contextual Stochastic Shortest Path (CSSP), where at the beginning of each episode, the learner observes an adversarially chosen context that determines the MDP through a fixed but unknown linear function. The learner's objective is to reach a designated goal state with minimal expected cumulative loss, despite having no prior knowledge of the transition dynamics, loss functions, or the mapping from context to MDP. In this work, we propose LR-CSSP, an algorithm that achieves a regret bound of $\widetilde{O}(K^{2/3} d^{2/3} |S| |A|^{1/3} B_\star^2 T_\star \log (1/ δ))$, where $K$ is the number of episodes, $d$ is the context dimension, $S$ and $A$ are the sets of states and actions respectively, $B_\star$ bounds the optimal cumulative loss and $T_\star$, unknown to the learner, bounds the expected time for the optimal policy to reach the goal. In the case where all costs exceed $\ell_{\min}$, LR-CSSP attains a regret of $\widetilde O(\sqrt{K \cdot d^2 |S|^3 |A| B_\star^3 \log(1/δ)/\ell_{\min}})$. Unlike in contextual finite-horizon MDPs, where limited knowledge primarily leads to higher losses and regret, in the CSSP setting, insufficient knowledge can also prolong episodes and may even lead to non-terminating episodes. Our analysis reveals that LR-CSSP effectively handles continuous context spaces, while ensuring all episodes terminate within a reasonable number of time steps.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。