The theory or approachability, introduced by Blackwell in 1956, provides fundamental results on guaranteed performance regions in repeated games with vector-valued payoffs. These results, which have been applied in theoretical work on learning in games, have recently been the subject of renewed int…
The theory or approachability, introduced by Blackwell in 1956, provides fundamental results on guaranteed performance regions in repeated games with vector-valued payoffs. These results, which have been applied in theoretical work on learning in games, have recently been the subject of renewed interest in the machine learning community due to their close connection with on-line learning algorithms. In this lecture, we will first review the basic approachability framework, outline its inter-connection with no-regret learning, and describe some applications to routing and scheduling. We will then describe some advances that include to new approachability algorithms, and their application to generalized no-regret problems.