CIF: SMALL: Theoretical Foundations of Partially Observable Reinforcement Learning: Minimax Sample Complexity and Provably Efficient Algorithms

许多强化学习（RL）系统在仅向代理提供部分观察和不完美信息的环境中运行。尽管在实证上取得了显着的成功，但部分可观察的强化学习模型仍然面临着相当大的理论挑战，可能对敏感任务构成重大风险。该项目将设计高效的学习算法，并为部分可观察的强化学习系统提供清晰的样本复杂性分析。理论工具将建立在广泛的学科基础上，包括机器学习、信息论、控制论和高维统计。所开发的成果将对机器人控制、自动驾驶和战略游戏等多种应用产生影响。研究人员致力于通过积极招募和培训学生来促进多样性，特别是那些来自科学、技术、工程和数学 (STEM) 领域代表性不足的少数族裔和女性的学生。该项目将解决学习两种部分可观察 RL 模型的理论挑战：部分可观察马尔可夫决策过程 (POMDP) 和扩展形式博弈 (EFG)。主要目标是为开发算法和证明尖锐的统计复杂性界限提供理论工具和新见解。第一个组成部分将重点关注 POMDP，其目标是缩小基本表格设置中学习的样本复杂性差距，并通过识别允许规划效率的结构条件来解决计算挑战。第二个部分将重点关注 EFG，目标是为三种类型的遗憾设计接近最优的算法：外部遗憾、Phi 遗憾和动态遗憾。所提出的算法和尖锐的统计复杂度界限将为强化学习理论家和实践者的未来研究提供坚实的理论基础。这些算法将在 OpenSpiel 环境中进行编码和测试，以评估其实证性能。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。

Many reinforcement learning (RL) systems operate within environments that provide only partial observations and imperfect information to the agents. Despite notable empirical success, partially observable RL models still present considerable theoretical challenges, potentially posing significant risks to sensitive tasks. This project will design efficient learning algorithms and provide sharp sample complexity analyses for partially observable RL systems. The theoretical tools will build on a broad range of subjects, including machine learning, information theory, control theory, and high-dimensional statistics. The developed results will have impact on a variety of applications such as robotic control, autonomous driving, and strategic games. The investigator is committed to fostering diversity by actively recruiting and training students, particularly those from underrepresented minorities and women in Science, Technology, Engineering, and Math (STEM).This project will tackle the theoretical challenges in learning two partially observable RL models: partially observable Markov decision processes (POMDPs) and extensive-form games (EFGs). The main goal is to provide theoretical tools and new insights to developing algorithms and proving sharp statistical complexity bounds. The first component will focus on POMDPs, with the goal of closing the sample complexity gap of learning in the basic tabular setting and addressing the computational challenges by identifying structural conditions that admit planning efficiency. The second component will focus on EFGs, with the goal of designing near-optimal algorithms for three types of regret: external regret, Phi-regret, and dynamic regret. The proposed algorithms and sharp statistical complexity bounds will provide a solid theoretical foundation for future research of RL theorists and practitioners. These algorithms will be coded and tested within the OpenSpiel environment to evaluate their empirical performance.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.