Understanding the Eluder Dimension
Understanding the Eluder Dimension
复制标题
DOI：
--
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Gen Li;Pritish Kamath;Dylan J. Foster;N. Srebro
中科院分区：
文献类型：
--
作者：
Gen Li;Pritish Kamath;Dylan J. Foster;N. Srebro
我们在躲避维度上提供了新的见解，这是一种被广泛用于约束在线盗贼算法和函数逼近强化学习遗憾的复杂性度量。首先，我们研究了函数类的逃逸维度与广义秩概念之间的关系，该概念定义为任意单调“激活”$\sigma：\mathbb{R}\to\mathbb{R}$，它对应于将函数类表示为广义线性模型所需的最小维度。已知，当$\sigma$的导数从$0$有界时，$\sigma$-秩会给出任意函数类的逃逸维度的上界；然而，我们证明了逃逸维度可以指数地小于$\sigma$-秩.我们还证明了关于导数的条件是必要的，即当$\sigma$是$\mathsf{relu}$激活时，逃逸维度可以指数地大于$\sigma$-ran.对于二进制值函数类，我们得到了关于星数和阈值维度的刻画，这两个量分别与主动学习和在线学习有关。
We provide new insights on eluder dimension, a complexity measure that has been extensively used to bound the regret of algorithms for online bandits and reinforcement learning with function approximation. First, we study the relationship between the eluder dimension for a function class and a generalized notion of rank, defined for any monotone"activation"$\sigma : \mathbb{R}\to \mathbb{R}$, which corresponds to the minimal dimension required to represent the class as a generalized linear model. It is known that when $\sigma$ has derivatives bounded away from $0$, $\sigma$-rank gives rise to an upper bound on eluder dimension for any function class; we show however that eluder dimension can be exponentially smaller than $\sigma$-rank. We also show that the condition on the derivative is necessary; namely, when $\sigma$ is the $\mathsf{relu}$ activation, the eluder dimension can be exponentially larger than $\sigma$-rank. For binary-valued function classes, we obtain a characterization of the eluder dimension in terms of star number and threshold dimension, quantities which are relevant in active learning and online learning respectively.