权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

CIF：SMALL：部分可观察强化学习的理论基础：最小最大样本复杂性和可证明有效的算法

基本信息

批准号：
2315725
负责人：
Song Mei
金额：
$ 48.37万
依托单位：
University of California-Berkeley
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2023
资助国家：
美国
起止时间：
2023-06-15 至 2026-05-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2315725&HistoricalAwards=false
关键词：
CIF SMALL Theoretical Foundations Partially

项目摘要

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.

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