提出可证明最优的协作游戏学习算法，实现高效人机协同决策。
Provably Optimal Learning Algorithms for Assistance Games
- 设计分布式算法，使人类与助手在未知环境中逐步优化共同目标。
- 实现近似率(1-1/e)、误差率约T^{3/4}的协助遗憾，优于传统方法。
- 适用于任何无后悔算法，且可借助共享随机串进一步提升性能。
本文研究在线协作游戏框架的变体，其中知情代理（人类）与不知情代理（助手）在 T 个时间步内反复交互以优化共同奖励函数。知情代理可观测世界隐状态，而不知情代理仅能观测人类动作。本文首次提出可证明高效的协作游戏学习算法。引入“协助遗憾”概念：交互累积效用与事后最优联合策略（将隐状态映射为动作对）之间的差距。提出人类与助手的去中心化算法，实现 (1-1/e) 近似协助遗憾率 ∼O(T^{3/4})，运行时间多项式依赖于动作与状态空间规模。该算法具有一般性，可兼容任意无后悔算法。证明：若逼近因子优于 (1-1/e)，则计算上不可行。此外，展示如何通过共享随机字符串，将算法扩展至伪去中心化设置，达到 ∼O(T^{1/2}) 的最优遗憾率（仅对数因子差异）。
原文摘要 · Abstract (English)
This paper studies an online variant of the assistance games framework, where an informed agent and an uninformed agent repeatedly interact over $T$ timesteps to optimize a common reward function. While the informed agent (the human) observes a latent state of the world, the uninformed agent (the assistant) observes only the human's actions. We provide the first provably efficient learning algorithms for repeated assistance games. We introduce the notion of assistance regret: the gap between the cumulative utility of interactions and that of the optimal joint policies in hindsight, which map latent states to action pairs. We present decentralized algorithms for both the human and the assistant that achieve a $(1-1/e)$-approximate assistance regret rate of $\widetilde{O}(T^{3/4})$, with runtime polynomial in the size of the action and state spaces. These algorithms are general; in particular, they accommodate any no-regret algorithm for the assistant. We prove that achieving a regret approximation factor better than $(1-1/e)$ is computationally intractable. Furthermore, we demonstrate how these generic no-regret algorithms can be tailored to a pseudo-decentralized setting -- using a shared random string -- to achieve a rate of $\widetilde{O}(T^{1/2})$, optimal up to logarithmic factors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。