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

In this paper we study the adversarial combinatorial bandit with a knownnon-linear reward function, extending existing work on adversarial linearcombinatorial bandit. {The adversarial combinatorial bandit with generalnon-linear reward is an important open problem in bandit literature, and it isstill unclear whether there is a significant gap from the case of linearreward, stochastic bandit, or semi-bandit feedback.} We show that, with $N$arms and subsets of $K$ arms being chosen at each of $T$ time periods, theminimax optimal regret is $\widetilde\Theta_{d}(\sqrt{N^d T})$ if the rewardfunction is a $d$-degree polynomial with $d< K$, and $\Theta_K(\sqrt{N^K T})$if the reward function is not a low-degree polynomial. {Both bounds aresignificantly different from the bound $O(\sqrt{\mathrm{poly}(N,K)T})$ for thelinear case, which suggests that there is a fundamental gap between the linearand non-linear reward structures.} Our result also finds applications toadversarial assortment optimization problem in online recommendation. We showthat in the worst-case of adversarial assortment problem, the optimal algorithmmust treat each individual $\binom{N}{K}$ assortment as independent.

Adversarial Combinatorial Bandits with General Non-linear Reward Functions