CIF: Small: Reinforcement Learning with Function Approximation: Convergent Algorithms and Finite-sample Analysis

最近，一种名为强化学习的机器学习技术在基准任务中取得了成功，这表明它在实际应用中有着潜在的革命性进展，并极大地提高了人们对这项技术的兴趣。然而，使用这种方法的常见算法数据效率极低，仅在模拟系统上才能产生令人印象深刻的结果，其中可以模拟无限数量的数据。例如，对于大多数人在几分钟内完成的在线任务，强化学习算法需要更长的时间才能达到人类水平的性能。一个好的强化学习算法“彩虹深度Q网络”需要大约1800万帧的模拟数据才能在最简单的在线任务中击败人类。这一数据量相当于约80人小时的在线体验。这种数据要求限制了强化学习算法在许多实际应用中的应用，这些应用只有有限的数据量。对于有效的强化学习需要多少数据的理论理解仍然非常有限。该项目旨在通过开发一种用于强化学习算法设计和分析收敛速度的综合方法来减少训练强化学习算法的数据需求，这反过来又会激励快速稳定的强化学习算法的设计。该项目将对各种工程和科学应用产生直接影响，例如，金融市场，商业战略规划，工业自动化和在线广告。该项目将采用优化和强化学习的工具和概念的新视角。下面的重点将按照难度递增的顺序进行研究。1)线性函数近似：将开发工具和见解，以解决控制问题中的非光滑性和非凸性挑战。2)一般函数逼近：非线性的新挑战将得到解决。3)神经函数逼近：收敛到全局和/或普遍最优解将被研究。在每一个三个推力，新的算法将被设计，其收敛速度将被表征。这些结果将进一步用作参数调整的指导方针，并激励快速收敛算法的设计。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

The recent success of a machine-learning technique called reinforcement learning in benchmark tasks suggests a potential revolutionary advance in practical applications, and has dramatically boosted the interest in this technique. However, common algorithms that use this approach are highly data-inefficient, leading to impressive results only on simulated systems, where an infinite amount of data can be simulated. For example, for online tasks that most humans pick up within a few minutes, reinforcement learning algorithms take much longer to reach human-level performance. A good reinforcement learning algorithm called "Rainbow deep Q-network" needs about 18 million frames of simulation data to beat human in performance for the simplest of online tasks. This amount of data corresponds to about 80 person-hours of online experience. This level of data requirements limits the application of reinforcement learning algorithms in many practical applications that only have a limited amount of data. Theoretical understanding of how much data is needed for effective reinforcement learning is still very limited. This project aims to reduce the data requirements to train reinforcement learning algorithms by developing a comprehensive methodology for reinforcement learning algorithm design and analyzing convergence rates, which will in turn motivate design of fast and stable reinforcement learning algorithms. This project will have a direct impact on various engineering and science applications, e.g., the financial market, business strategy planning, industrial automation and online advertising.This project will take a fresh perspective of using tools and concepts from both optimization and reinforcement learning. The following thrusts will be investigated in an increasing order of difficulty. 1) Linear function approximation: tools and insights will be developed to tackle challenges of non-smoothness and non-convexity in control problems. 2) General function approximation: new challenge of non-linearity will be addressed. 3) Neural function approximation: convergence to globally and/or universally optimal solutions will be investigated. In each of the three thrusts, new algorithms will be designed, and their convergence rates will be characterized. These results will be further used as guideline for parameter tuning, and to motivate design of fast and convergent algorithms.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.