
15-888 Computational Game Solving (Fall 2021) Thu, September 30th 2021
Lecture 8
Predictive Blackwell approachability
Instructor: Gabriele Farina
In Lecture 4 we constructed a regret minimizer, called Regret Matching, by solving a suitable Blackwell
approachability game. In this lecture, we will do the opposite: we will investigate how regret minimization
algorithm can give rise to Blackwell approachability algorithms. From there, we use predictive regret
minimization algorithms to arrive at predictive Blackwell approachability algorithms.
1 Using regret minimization to solve Blackwell approachability games
Recall that a Blackwell approachability game is a tuple (X , Y, u, S), where X , Y are closed convex sets,
u : X × Y d is a biaffine function, and S d is a closed and convex target set. A Blackwell
approachability game represents a vector-valued repeated game between two players. At each time t, the two
payers interact in this order:
first, Player 1 selects an action xt ∈ X ;
then, Player 2 selects an action yt ∈ Y, which can depend adversarially on all the xt output so far;
finally, Player 1 incurs the vector-valued payoff u(xt, yt) d, where u is a biaffine function.
Player 1’s objective is to guarantee that the average payoff converges to the target set S. Formally, given target
set S d, Player 1’s goal is to pick actions x1, x2, . . . ∈ X such that no matter the actions y1, y2, . . . ∈ Y
played by Player 2,
min
ˆsS




ˆs 1
T
T
t=1
u(xt, yt)




2
0 as T → ∞. (1)
As we discussed in Lecture 4, Blackwell’s theorem states that goal (1) can be attained if and only if any
halfspace H ⊇ S is forceable, where forceability is recalled next.
Definition 1.1 (Forceable halfspace). Let (X , Y, u, S) be a Blackwell approachability game and let H ⊆ d
be a halfspace, that is, a set of the form H = {x d : a>x b} for some a d, b . The halfspace
H is said to be forceable if there exists a strategy of Player 1 that guarantees that the payoff is in H no
matter the actions played by Player 2, that is, if there exists x ∈ X such that
u(x, y) ∈ H y ∈ Y.
When that is the case, we call action x a forcing action for H.
Abernethy et al. [2011] showed that it is always possible to convert a regret minimizer into an algorithm
for a Blackwell approachability game (that is, an algorithm that chooses actions xt at all times t in such a way
that goal (1) holds no matter the actions y1, y2, . . . played by the opponent).(Gordon’s Lagrangian Hedging
[Gordon, 2005, 2006] partially overlaps with the construction by Abernethy et al. [2011].)
1.1 A couple preliminaries on convex cones
For simplicity, we will only be interested in Blackwell games whose target sets are (nonempty) closed convex
cones S n.
Definition 1.2. A cone is a set such that for any point s S, the rescaled point λs belongs to S for any
λ 0. In particular, 0 S for any nonempty cone.
Cones have a very regular geometry that will make constructing approachability algorithms simpler. This
simplicity actually doesn’t come at a generality cost: one of the contributions of Abernethy et al. [2011] is to
show that any Blackwell approachability game with non-conic target set can be studied and solved by first
transforming the problem into a slightly larger Blackwell approachability game with conic target set.
A standard concept in conic geometry is that of the polar cone, which we now define.
Definition 1.3. The polar of cone S, denotes S, is defined as the set of all vectors that form an obtuse
angle with the cone S, that is,
S := {w n : w>s 0 s S}.
The polar S is itself a closed and convex cone provided that S is a closed and convex cone.
The reason we care about the polar of S is that it gives a characterization of important halfspaces H ⊇ S,
which are so crucial to Blackwell’s theorem.
Lemma 1.1. Let θ S and consider the halfspace Hθ := {x n : θ>x 0}. Then, Hθ S.
Proof. Take any s S; we will show that s ∈ Hθ . Since θ S, by definition of polar cone we have that
θ>s 0 for all s S, including in particular s = s. So, s ∈ Hθ as we wanted to show.
1.2 Abernethy et al. [2011]’s idea
Blackwell’s algorithm described in Lecture 4 worked by playing, at every time t, a forcing actions for the
halfspace tangent to S at the projection point ψt S of the current average payoff ̄φt := 1
T
t1
τ =1 u(xt, yt).
Abernethy et al. [2011]’s idea is to generalize this construction by letting a regret minimizer decide which
halfspace to force.
Specifically, let RS be a regret minimizer that outputs strategies θt S that observes as utilities the
Blackwell payoffs `t := u(xt, yt). At every time t, we will force the halfspace
Hθt := {x n : (θt)>x 0},
which, as we discussed in Lemma 1.1, is a superset of the target set S (see also Figure 1).
Algorithm 1: From regret minimization to Blackwell approachability
Data: RS regret minimizer for S
1 function NextStrategy()
2 θt ← RS .NextStrategy()
3 return xt forcing action for Hθt := {x : (θt)>x 0}
4 function ReceivePayoff(u(xt, yt))
5 RS .ObserveLoss(`t := u(xt, yt))
S
S
θt
Hθt
Figure 1: Pictorial depiction of Algorithm 1’s inner working: at all times t, the algorithm plays a forcing
action for the halfspace Ht induced by the last decision output by L.
The proof of correctness for Algorithm 1 relies on this lemma that shows that the problem of minimizing
distance to a cone is equivalent to the problem of maximizing the inner product on the polar of the cone.
Lemma 1.2. Let S n be a cone and z be a generic point in n. Then,
min
ˆsS ˆs z2 = max
ˆθS n
2
z> ˆθ,
where n
2 := {x n : x2 1} denotes the unit ball in n with respect to the Euclidean norm.
Proposition 1.1. Denote the regret of RS compared to any ˆθ as
RT
S ( ˆθ) :=
T
t=1
(`t)> ˆθ
T
t=1
(`t)>θt.
Then, at all times T , the distance between the average payoff cumulated by Algorithm 1 and the target
cone S is upper bounded as
min
ˆsS




ˆs 1
T
T
t=1
u(xt, yt)




2
1
T max
ˆθS n
2
RT
S ( ˆθ),
where n
2 denotes the unit ball in n with respect to the Euclidean norm, just like in Lemma 1.2.
Proof. Using Lemma 1.2,
min
ˆsS




ˆs 1
T
T
t=1
u(xt, yt)




2
= max
ˆθS n
2
(
1
T
T
t=1
u(xt, yt)
)>
ˆθ = max
ˆθSn
2
(
1
T
T
t=1
`t
)>
ˆθ
= 1
T max
ˆθS n
2
{ T
t=1
(`t)> ˆθ
}
(2)
where the second step uses `t := u(xt, yt). By substituting the definition RT
S ( ˆθ) into (2), we then find
min
ˆsS




ˆs 1
T
T
t=1
u(xt, yt)




2
= 1
T max
ˆθS n
2
{
RT
S ( ˆθ) +
T
t=1
(`t)>θt
}
= 1
T max
ˆθS n
2
{
RT
S ( ˆθ)
}
+ 1
T
T
t=1
(`t)>θt.
Now, by construction xt is a forcing action for the halfspace Hθt = {x n : (θt)>x 0}, and so
(θt)>u(xt, yt) = (`t)>θt 0. Hence,
1
T
T
t=1
(`t)>θt 0. (3)
Plugging (3) into (2) yields the statement.
Proposition 1.1 immediately implies that if the regret minimizer RS is able to guarantee that the regret on
the subset S n
2 of its domain S grows sublinearly, then goal (1) can be attained.
Algorithms that are able to guarantee that max ˆθS n
2
RT
S ( ˆθ) = o(T ) exist. For example, if RS is set to
OMD or FTRL with Euclidean regularization, then it can be shown that
max
ˆθS n
2
RT
S ( ˆθ)



2
( T
t=1
`t2
2
)
,
which clearly grows at a sublinear rate of O(T ).
2 Predictive Blackwell Approachability
Predictive Blackwell approachability is a natural extension of Blackwell approachability [Farina et al., 2021].
Similarly to how we defined predictive regret minimization, in predictive Blackwell approachability the
environment provides Player 1 with a prediction vt of the next utility u(xt, yt).
It is immediate to extend the construction of Abernethy et al. [2011] (Algorithm 1) to take into account
predictions: since the utility observed by RS (Line 5) is exactly ut(xt, yt), we can simply use a predictive
regret minimization algorithm RS and provide vt as the prediction of the next utility. The predictive version
of Algorithm 1 is given in Algorithm 2.
The analysis in Proposition 1.1 holds verbatim. In fact, it can be shown that when RS is set to predictive
OMD or FTRL with Euclidean regularization, then
max
ˆθS n
2
RT
S ( ˆθ)



2
( T
t=1
`t vt2
2
)
,
which clearly grows at a sublinear rate of O(T ) and can be very small if the predictions vt are accurate.
Algorithm 2: Predictive Blackwell approachability algorithm
Data: RS predictive regret minimizer for S
1 function NextStrategy(vt)
[. vt is the prediction of the next Blackwell payoff u(xt, yt) n]
2 θt ← RS .NextStrategy(vt)
3 return xt forcing action for Hθt := {x : (θt)>x 0}
4 function ReceivePayoff(u(xt, yt))
5 RS .ObserveLoss(`t := u(xt, yt))
References
Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are
equivalent. In Proceedings of the Conference on Learning Theory (COLT), pages 27–46, 2011.
Geoffrey J. Gordon. No-regret algorithms for structured prediction problems. Technical Report CMU-CALD-
05-112, Carnegie Mellon University, 2005.
Geoffrey J Gordon. No-regret algorithms for online convex programs. Advances in Neural Information
Processing Systems, 19:489, 2006.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive Blackwell
approachability: Connecting regret matching and mirror descent. Proceedings of the AAAI Conference on
Artificial Intelligence (AAAI), 2021.

Content

PDF File

Typo or question?

Get in touch!
gfarina AT mit.edu

Metadata

Course: CMU 15-888
Term: Fall 2021
Date: 2021-09-30