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

Approachability theory, introduced by Blackwell (1956), provides fundamentalresults on repeated games with vector-valued payoffs, and has been usefullyapplied since in the theory of learning in games and to learning algorithms inthe online adversarial setup. Given a repeated game with vector payoffs, atarget set $S$ is approachable by a certain player (the agent) if he can ensurethat the average payoff vector converges to that set no matter what hisadversary opponent does. Blackwell provided two equivalent sets of conditionsfor a convex set to be approachable. The first (primary) condition is ageometric separation condition, while the second (dual) condition requires thatthe set be {\em non-excludable}, namely that for every mixed action of theopponent there exists a mixed action of the agent (a {\em response}) such thatthe resulting payoff vector belongs to $S$. Existing approachability algorithmsrely on the primal condition and essentially require to compute at each stage aprojection direction from a given point to $S$. In this paper, we introduce anapproachability algorithm that relies on Blackwell's {\em dual} condition.Thus, rather than projection, the algorithm relies on computation of theresponse to a certain action of the opponent at each stage. The utility of theproposed algorithm is demonstrated by applying it to certain generalizations ofthe classical regret minimization problem, which include regret minimizationwith side constraints and regret minimization for global cost functions. Inthese problems, computation of the required projections is generally complexbut a response is readily obtainable.

Response-Based Approachability and its Application to Generalized No-Regret Algorithms