Tech Report CS-06-01

Blackwell's Approachability Theorem: A Generalization in a Special Case

Amy Greenwald, Amir Jafari and Casey Marks

January 06

Abstract:

Blackwell's seminal approachability theorem provides a sufficient condition to ensure that, in a vector-valued repeated game, a learner's average rewards approach any closed and convex subset of finite-dimensional Euclidean space. In this paper, we prove a close cousin of Blackwell's theorem. On the one hand, our theorem specializes Blackwell's theorem: it provides a sufficient condition for the negative orthant to be approachable, rather than an arbitrary closed and convex subset of finite-dimensional Euclidean space. On the other hand, our sufficient condition is weaker than Blackwell's original condition: our condition need only hold for some real-valued constant, rather than precisely for zero. Moreover, in our framework, the opponents (i.e., not the learner) have at their disposal an arbitrary, not merely a finite, set of actions.

(complete text in pdf)