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

Partial monitoring games are repeated games where the learner receivesfeedback that might be different from adversary's move or even the rewardgained by the learner. Recently, a general model of combinatorial partialmonitoring (CPM) games was proposed \cite{lincombinatorial2014}, where thelearner's action space can be exponentially large and adversary samples itsmoves from a bounded, continuous space, according to a fixed distribution. Thepaper gave a confidence bound based algorithm (GCB) that achieves$O(T^{2/3}\log T)$ distribution independent and $O(\log T)$ distributiondependent regret bounds. The implementation of their algorithm depends on twoseparate offline oracles and the distribution dependent regret additionallyrequires existence of a unique optimal action for the learner. Adopting theirCPM model, our first contribution is a Phased Exploration with GreedyExploitation (PEGE) algorithmic framework for the problem. Different algorithmswithin the framework achieve $O(T^{2/3}\sqrt{\log T})$ distribution independentand $O(\log^2 T)$ distribution dependent regret respectively. Crucially, ourframework needs only the simpler "argmax" oracle from GCB and the distributiondependent regret does not require existence of a unique optimal action. Oursecond contribution is another algorithm, PEGE2, which combines gap estimationwith a PEGE algorithm, to achieve an $O(\log T)$ regret bound, matching the GCBguarantee but removing the dependence on size of the learner's action space.However, like GCB, PEGE2 requires access to both offline oracles and theexistence of a unique optimal action. Finally, we discuss how our algorithm canbe efficiently applied to a CPM problem of practical interest: namely, onlineranking with feedback at the top.

Phased Exploration with Greedy Exploitation in Stochastic Combinatorial Partial Monitoring Games