English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present a non-asymptotic lower bound on the eigenspectrum of the designmatrix generated by any linear bandit algorithm with sub-linear regret when theaction set has well-behaved curvature. Specifically, we show that the minimumeigenvalue of the expected design matrix grows as $\Omega(\sqrt{n})$ wheneverthe expected cumulative regret of the algorithm is $O(\sqrt{n})$, where $n$ isthe learning horizon, and the action-space has a constant Hessian around theoptimal arm. This shows that such action-spaces force a polynomial lower boundrather than a logarithmic lower bound, as shown by \cite{lattimore2017end}, indiscrete (i.e., well-separated) action spaces. Furthermore, while the previousresult is shown to hold only in the asymptotic regime (as $n \to \infty$), ourresult for these "locally rich" action spaces is any-time. Additionally, undera mild technical assumption, we obtain a similar lower bound on the minimumeigen value holding with high probability.  We apply our result to two practical scenarios -- \emph{model selection} and\emph{clustering} in linear bandits. For model selection, we show that anepoch-based linear bandit algorithm adapts to the true model complexity at arate exponential in the number of epochs, by virtue of our novel spectralbound. For clustering, we consider a multi agent framework where we show, byleveraging the spectral result, that no forced exploration is necessary -- theagents can run a linear bandit algorithm and estimate their underlyingparameters at once, and hence incur a low regret.

Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference