arXiv cs.LG· Haolin Liu, Chen-Yu Wei, Hanbin Zhou·· 11 天前AI 评分27
对抗性线性马尔可夫决策过程在聚合老虎机反馈下的首个多项式时间最优遗憾算法
A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback
AI 导读
研究人员提出了针对具有未知转移、对抗性损失和老虎机反馈的分幕式线性马尔可夫决策过程（MDP）的首个多项式时间算法，实现了最优的 $\sqrt{K}$ 遗憾界（$K$ 为分幕数）。该方法通过构建近似分离预言机，将对抗性线性 MDP 规约到动作集未知的对抗性线性老虎机问题。该算法仅需聚合损失反馈，也是对抗性 MDP 在非表格化设定下首个支持聚合反馈的多项式时间算法。
来源：arXiv cs.LG · arxiv.org