Blackwell's Approachability and Online Convex Optimization: Some New Relations

David Blackwell introduced in 1956 the problem of set-approachability in repeated games with vector payoffs, along with geometric approachability conditions and corresponding strategies that rely on computing "steering directions" as projections from the current average-payoff vector to the target set. An alternative framework for generating these steering directions has recently been proposed, which relies on the modern theory of no-regret algorithms and online convex optimization, along with some basic relations from convex analysis. In this talk we will describe this general framework, derive some concrete algorithms along with their performance, and finally explore some useful relations to Blackwell's original algorithm. The required background on approachability and on Online Convex Optimization will be provided as well.