Understanding the Eluder Dimension
  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.
