Tata Institute of Fundamental Research

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

STCS Seminar
Speaker: Nahum Shimkin (Technion Israel Institute of Technology Department of Electrical Engineering Technion City Haifa 32000 Israel)
Organiser: Sandeep K Juneja
Date: Tuesday, 3 Mar 2015, 16:00 to 17:00
Venue: D-405 (D-Block Seminar Room)

(Scan to add to calendar)
Abstract:  Abstract: 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.