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 study the optimal batch-regret tradeoff for batch linear contextualbandits. For any batch number $M$, number of actions $K$, time horizon $T$, anddimension $d$, we provide an algorithm and prove its regret guarantee, which,due to technical reasons, features a two-phase expression as the time horizon$T$ grows. We also prove a lower bound theorem that surprisingly shows theoptimality of our two-phase regret upper bound (up to logarithmic factors) inthe \emph{full range} of the problem parameters, therefore establishing theexact batch-regret tradeoff.  Compared to the recent work \citep{ruan2020linear} which showed that $M =O(\log \log T)$ batches suffice to achieve the asymptotically minimax-optimalregret without the batch constraints, our algorithm is simpler and easier forpractical implementation. Furthermore, our algorithm achieves the optimalregret for all $T \geq d$, while \citep{ruan2020linear} requires that $T$greater than an unrealistically large polynomial of $d$.  Along our analysis, we also prove a new matrix concentration inequality withdependence on their dynamic upper bounds, which, to the best of our knowledge,is the first of its kind in literature and maybe of independent interest.

Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits