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

A recurring theme in statistical learning, online learning, and beyond isthat faster convergence rates are possible for problems with low noise, oftenquantified by the performance of the best hypothesis; such results are known asfirst-order or small-loss guarantees. While first-order guarantees arerelatively well understood in statistical and online learning, adapting to lownoise in contextual bandits (and more broadly, decision making) presents majoralgorithmic challenges. In a COLT 2017 open problem, Agarwal, Krishnamurthy,Langford, Luo, and Schapire asked whether first-order guarantees are evenpossible for contextual bandits and -- if so -- whether they can be attained byefficient algorithms. We give a resolution to this question by providing anoptimal and efficient reduction from contextual bandits to online regressionwith the logarithmic (or, cross-entropy) loss. Our algorithm is simple andpractical, readily accommodates rich function classes, and requires nodistributional assumptions beyond realizability. In a large-scale empiricalevaluation, we find that our approach typically outperforms comparablenon-first-order methods.  On the technical side, we show that the logarithmic loss and aninformation-theoretic quantity called the triangular discrimination play afundamental role in obtaining first-order guarantees, and we combine thisobservation with new refinements to the regression oracle reduction frameworkof Foster and Rakhlin. The use of triangular discrimination yields novelresults even for the classical statistical learning model, and we anticipatethat it will find broader use.

Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination