Conference On Learning Theory

VIP内容

在过去的十年中,人们对不确定性下的连续决策产生了极大的兴趣,这是一类涉及到智能体与未知环境交互以实现某些目标的广泛问题。强化学习方法解决了这些问题,最近人工智能在游戏、机器人等领域取得了突破。受这些实证证明的启发,许多学习理论界的研究人员将他们的注意力转向了强化学习,试图更好地理解这些问题并发展新的算法原则。他们的努力为强化学习带来了一个更现代的统计基础,强调通过全局收敛、样本复杂性和遗憾分析的非渐近特征。

本教程将概述这一新兴理论,重点是最具挑战性的在线探索设置。本教程分为三个部分:

第一部分将介绍必要的背景知识和定义。我们在这里重点讨论了表式马尔可夫决策过程的最基本设置,并考虑了难度不断增加的问题:从规划,到基于探索性分布的优化,再到在线探索。我们将提出两种算法:用于优化问题的自然策略梯度(NPG)和用于探索的ucb -值迭代(UCB-VI),以及它们的保证。

第二部分是复习/实践习部分。我们准备了一个问题集,涵盖了NPG和UCB-VI的详细分析,突出了在强化学习中广泛有用的关键引理,以及与相关领域的技术联系。这次会议将集体举行。许多该领域的专家将会在问题集上提供帮助或回答其他问题。

第三部分将着重于表格设置之外的在线探索,在表格设置中需要函数近似来进行泛化。在这里,我们将提供一个RL模型和复杂性度量的合集,使易于处理的学习,以及一些统计障碍和算法。最后,我们将讨论一些尚未解决的问题和未来的方向。

所有COLT参与者都可以访问本教程。不需要RL的背景知识,但我们希望教程参与者能够熟练使用学习理论研究中使用的标准数学工具,如集中不等式和一些线性代数。

https://rltheorybook.github.io/colt21tutorial

成为VIP会员查看完整内容
0
28

最新论文

We introduce the $(p,q)$-Fair Clustering problem. In this problem, we are given a set of points $P$ and a collection of different weight functions $W$. We would like to find a clustering which minimizes the $\ell_q$-norm of the vector over $W$ of the $\ell_p$-norms of the weighted distances of points in $P$ from the centers. This generalizes various clustering problems, including Socially Fair $k$-Median and $k$-Means, and is closely connected to other problems such as Densest $k$-Subgraph and Min $k$-Union. We utilize convex programming techniques to approximate the $(p,q)$-Fair Clustering problem for different values of $p$ and $q$. When $p\geq q$, we get an $O(k^{(p-q)/(2pq)})$, which nearly matches a $k^{\Omega((p-q)/(pq))}$ lower bound based on conjectured hardness of Min $k$-Union and other problems. When $q\geq p$, we get an approximation which is independent of the size of the input for bounded $p,q$, and also matches the recent $O((\log n/(\log\log n))^{1/p})$-approximation for $(p, \infty)$-Fair Clustering by Makarychev and Vakilian (COLT 2021).

0
0
下载
预览
Top