Repeated Games with Vector Losses: A Set-valued Dynamic
Programming Approach

arXiv:1603.04981v4 [cs.GT] 7 Jan 2018

Vijay Kamble∗

Patrick Loiseau†

Jean Walrand‡

January 9, 2018

Abstract
We consider infinitely repeated games with vector losses discounted over time. We characterize the set of minimal upper bounds on expected losses that a player can simultaneously
guarantee across the different dimensions. Specifically, we show that this set is the fixed point
of a set-valued dynamic programming operator. This approach also characterizes the strategies
that achieve these bounds. These optimal strategies are shown to be independent of the player’s
own past actions and stationary relative to a compact state space obtained by parameterizing
the set of the minimal bounds. We also present a computational procedure to approximate this
set and the optimal strategies.
We discuss two applications of our results: 1) characterization of the optimal strategy of
the uninformed player in zero-sum discounted repeated games with incomplete information on
one side; 2) characterization of the minmax optimal regret and the regret-optimal strategy in
repeated games with discounted losses. Our approximation procedure can be used to compute
approximately optimal strategies in both these applications. We illustrate this procedure by
computing approximately regret-optimal strategies for the problem of prediction using expert
advice from two and three experts under {0, 1}−losses. Our numerical evaluations demonstrate
improved performance over existing algorithms for this problem.

1

Introduction.

In several decision-making scenarios in uncertain and potentially adversarial environments, a decisionmaker cares about multiple objectives at the same time. For example, in certain defense operations,
an agent might be interested in simultaneously defending multiple targets against an enemy. In a
repeated game against an unknown opponent, a player wants to perform well relative to each strategy in some given class, in hindsight. In dynamic asymmetric information games where a player
lacks some information that other players have, a natural approach for the player is to choose a
strategy that gives appropriate worst-case guarantees simultaneously across the different underlying
possibilities. One can model many of these scenarios as a vector-valued sequential game between
the agent and an adversary.
∗

Dept. of Information and Decision Sciences, University of Illinois at Chicago (kamble@uic.edu)
Univ. Grenoble Alpes, CNRS, INRIA, Grenoble INP, LIG, France, and, Max-Planck Institute for Software
Systems (MPI-SWS), Germany (patrick.loiseau@univ-grenoble-alpes.fr)
‡
Dept. of Electrical Engineering and Computer Science, University of California, Berkeley (walrand@berkeley.edu)
†

1

In this paper we focus on two-player repeated games with vector-valued losses, which is one of the
simplest classses of such sequential games. We give a systematic set-valued dynamic programming
approach for characterizing the lower Pareto frontier of the set of upper bounds on expected losses
that a player can simultaneously guarantee across the different dimensions. For the case of infinitely
repeated games with discounted losses, we characterize this Pareto frontier as the fixed point of a setvalued dynamic programming operator. This operator also characterizes the strategies that achieve
the different points on the frontier, which gives us hitherto unknown insights into the structure of
these optimal strategies. Finally, we leverage this characterization to propose an approximate
dynamic programming based scheme to approximate the optimal frontier and to compute simple
approximately optimal strategies.
Blackwell [10] pioneered the study of two-player vector-valued repeated games, resulting in the
“Blackwell Approachability” framework. This framework gives sufficient conditions for any convex
set of loss vectors to be approachable by a player, which means that there exists a strategy for the
player that ensures that the long-run average loss approaches this set with probability 1 regardless
of the adversary’s actions. Blackwell also defined an adaptive randomized strategy that ensures
this. Further, he proved the following remarkable “minmax” theorem: any convex set is either
approachable by the player or is excludable by the adversary, which means that the adversary has
a strategy that ensures that the long-run average loss remains outside this set with probability 1.
Approachability theory has been subsequently extended in various ways [39, 28, 33, 20]. However, the lack of both a “classical” dynamic programming based development of the ideas and the
corresponding characterizations of achievable sets for the case of discounted losses has remained
a significant theoretical gap. This paper takes a major step towards bridging this gap between
Bellman’s and Blackwell’s paradigms. A minmax theorem à la Blackwell isn’t expected to hold
for discounted losses. For instance, it doesn’t hold for finite scalar games, as we show in Appendix E. Nevertheless, our theory characterizes the minimal lower corner sets, i.e., sets of the
form {x ∈ RK : xk ≤ ak }, that can be guaranteed by a single player in the discounted repeated
game. That is, given any lower corner set, our characterization yields the answer to the query: can
the player guarantee that the expected loss vector remains within this set irrespective of the actions
of the adversary? Analogous questions for general convex polytopes of the form {x ∈ RK : Ax ≤ b}
can be answered by considering games with appropriate linear transformations of the vector losses.
Consequently, our approach bridges corresponding important gaps in other decision-making
problems where vector-valued repeated games and Blackwell’s approachability theory have found
applications. We focus on two particularly significant such applications. The first application is to
the theory of zero-sum discounted repeated games with lack of information on one side [6], where
our approach yields previously unknown insights into the structure of the optimal strategy for the
uninformed player. The second application is to the paradigm of regret minimization in repeated
games, where our theory results in the first exact characterization of the optimal regret and the
regret-optimal strategy for the case of discounted losses. We discuss both these applications in
detail.
Finally, we mention that set-valued dynamic programs have been used in other contexts in the
theory of dynamic games, for instance to compute the set of equilibrium payoffs in non-zero sum
repeated games with imperfect monitoring [3, 4]. For the use of dynamic programming in zero-sum
dynamic games one can refer to the classic paper by Shapley [36] on stochastic games. For a general
theory of dynamic programming in control problems and Markov decision processes (MDPs), see
[8, 9, 34].
The paper is organized as follows. In Section 2, we formally introduce the model of repeated
2

games with vector valued losses and define the objective of characterizing the set of losses that
can be guaranteed by a player. In Section 3, we introduce the set-valued dynamic programming
approach for characterizing these guarantees and the corresponding optimal strategies. In Section 4,
we present an approximation procedure to compute an -optimal strategy. Section 5 presents the
application to zero-sum repeated games with incomplete information on one side. Section 6 discusses
the application of our approach to regret minimization in repeated games. Section 7 concludes the
paper. The proofs of all our claims are presented in the appendix.

2

Model.

Consider a two-player vector-valued game G defined by an action set A = {1, · · · , m} for player
1, who is the decision-maker and whom we will call Alice, and the action set B = {1, · · · , n} for
player 2 who is the adversary and whom we will call Bob. For each pair of actions a ∈ A and b ∈ B,
Alice incurs a vector-valued loss r(a, b) ∈ RK .

The game G is played repeatedly in stages t = 1, 2, 3, · · · , T . Let GT denote this T -stage repeated
game. In each stage t, both Alice and Bob simultaneously pick their actions at and bt respectively,
and Alice bears the vector of losses r(at , bt ). Fix a discount factor β ∈ [0, 1). Then the vector of
total discounted losses is defined as:
X

T
T
X
t−1
t−1
β r(at , bt ) =
β rk (at , bt ); k = 1, · · · , K .
(1)
t=1

t=1

An adaptive randomized strategy πA for Alice specifies for each stage t, a mapping from the set
of observations till stage t, i.e., Ht = (a1 , b1 , · · · , at−1 , bt−1 ), to a probability distribution on the
action set A, denoted by ∆(A). Let ΠA be the set of all such strategies of Alice. Similarly, let ΠB
be the set of all adaptive randomized strategies for Bob. For a pair of strategies πA and πB , the
expected discounted loss on component k in the repeated game is given by:
RkT (πA , πB )

= EπA ,πB

X
T

β

t−1


rk (at , bt ) ,

(2)

t=1

where the expectation is over the randomness in the strategies πA and πB . Alice would like to
minimize her loss in every component k. However, reducing the loss in one dimension typically
implies increasing the loss in another dimension. For instance, consider the situation of protecting
two different targets against attacks: devoting more resources to protect one target makes the other
more vulnerable. Accordingly, it is important to characterize the set of best possible tradeoffs
between the different dimensions of the loss.
Now consider a fixed strategy πA ∈ ΠA . If Alice plays this strategy, then irrespective of the
strategy chosen by Bob, Alice guarantees that the long term expected vector loss is no larger than


T
k
max Rk (πA , πB ); k = 1, · · · , K
k ∈Π
πB
B

along each dimension. Let the set of all such simultaneous upper bounds that correspond to all the
strategies πA ∈ ΠA be defined as:



T
T
k
W ,
max Rk (πA , πB ); k = 1, · · · , K : πA ∈ ΠA .
(3)
k ∈Π
πB
B

3

Then characterizing the best possible tradeoffs across the different dimensions amounts to finding
the minimal points in the set W, i.e., its lower Pareto frontier, which is the set
VT , Λ(WT ) , {x ∈ WT : ∀ x0 ∈ WT \ {x}, ∃ k s.t. xk < x0k },

(4)

since all other points are strictly sub-optimal. Our goal in this paper is to characterize and compute
the set V∞ that can be achieved in the infinite horizon game G∞ and compute strategies for Alice
in ΠA that achieve different points in it. Our main technical contributions are as follows:
1. We show that the set V∞ is the fixed point of a set-valued dynamic programming operator
defined on the space of lower Pareto frontiers of closed convex sets with an appropriately
defined metric. We then show that the optimal strategies that guarantee different points in
this set are of the following form. V∞ can be parametrized so that each point corresponds
to a parameter value, which can be thought of as an “information state” belonging to a
compact space. Each state is associated with an immediate optimal randomized action and a
transition rule that depends on the observed action of the adversary (but not on the Alice’s
own action). In order to attain a point in V∞ , Alice starts with the corresponding state, plays
the associated randomized action, transitions into another state depending on Bob’s observed
action as dictated by the rule, plays the randomized action associated with the new state and
so on. In particular, the strategy does not depend on Alice’s own actions and it depends on
Bob’s actions only through this state that Alice keeps track of.
2. We also give a procedure to approximate V∞ and to compute an approximately optimal
strategy that only uses a coarse finite quantization of the parameter space. This strategy
can be simply implemented by a randomized finite-state automaton. Any desired diminishing
approximation error can be attained by choosing the appropriate quantization granularity
and number of iterations.

3

Set-valued dynamic programming.

We first present an informal description of our approach. Let V0 = {0}, i.e., the singleton set
containing only the zero vector in RK . We can show that one can obtain the set VT +1 from the set
VT , by decomposing Alice’s strategy in GT +1 into a strategy for the 1st stage, and a continuation
strategy for the remainder of the game from stage 2 onwards as a function of the action chosen by
both the players in the 1st stage. The inductive argument results from the fact that the minimal
guarantees that she can guarantee from stage 2 onwards are exactly the set VT . Suppose that at
the start of GT +1 , Alice fixes the following plan for the entire game: she will play a mixed strategy
α ∈ ∆(A) in stage 1. Then depending on her realized action a and Bob’s action b, from stage
2 onwards she will play a continuation strategy that achieves the upper-bound R(a, b) ∈ VT (she
will choose one such point R(a, b) for every a ∈ A and b ∈ B). Note that it is strictly sub-optimal
for Alice to choose any points outside VT from stage 2 onwards. Now this plan for the entire
game GT +1 gives Alice the following simultaneous upper bounds on the expected losses on the K
dimensions:

max
b∈B

X
a∈A



αa rk (a, b) + βRk (a, b) ; k = 1, · · · , K .


4

By varying the choice of α and the map R(a, b) we can obtain the set of all the simultaneous upper
bounds that Alice can achieve in the (T + 1)-stage game. The Lower Pareto frontier of this set is
exactly VT +1 . Thus there is an operator Φ, such that
VT +1 = Φ(VT )
for any T ≥ 0. In what follows, we will show that this operator is a contraction in the space of lower
Pareto frontiers of compact and convex sets, with an appropriately defined metric. This space is
shown to be complete, and thus the sequence VT converges in the metric to a set V∗ , which is the
unique fixed point of this operator Φ. As one would guess, this V∗ is indeed the set V∞ of minimal
simultaneous upper bounds that Alice can achieve in the infinitely repeated game G∞ .
The rest of this section formalizes these arguments. We will begin the formal presentation of
our results by first defining the space of Pareto frontiers that we will be working with.

3.1

A space of Pareto frontiers in [0, 1]K

For the remainder of the paper, 1 and 0 denote the the vector of ones and zeros, respectively, in
RK .
Definition 3.1. (a) Let u, v ∈ RK . We say that u  v if uk ≤ vk for all k. Also, we say that
u ≺ v if u  v and u 6= v. For some  ≥ 0 if u  v + 1, we say that v -dominates u. If  = 0,
we simply say that v dominates u.
(b) A Pareto frontier in [0, 1]K is a subset V of [0, 1]K such that no v ∈ V is dominated by
another element of V.
(c) For two Pareto Frontiers U and V, we say that V -dominates U if for every point v ∈ V,
there is a point u ∈ U that it -dominates. If  = 0, then we simply say that V dominates U.

(d) The lower Pareto frontier (or simply Pareto frontier) of S ⊂ [0, 1]K , denoted by Λ(S), is the
set of elements of S that do not dominate any another element of S.
The Pareto frontier of a set may be empty, as is certainly the case when the set is open. But
one can show that the Pareto frontier of a compact set is always non-empty. The proof is presented
in the Appendix A.
Lemma 3.1. Suppose that S is a compact subset of RK . Then Λ(S) is non-empty.
Since compactness is equivalent to a set being closed and bounded in Euclidean spaces, any closed
subset of [0, 1]K has a non-empty Pareto frontier. We next define the upset of a set, illustrated in
Figure 1.
Definition 3.2. Let A be a subset of B ⊆ RK . The upset of A in B is defined as up(A) = {x ∈
B | xk ≥ yk for all k, for some y ∈ A}, i.e., up(A) is the set of all points in B that dominate some
point in A. Equivalently, up(A) = {x ∈ B | x = y + v, for some y ∈ A and v  0}.
For a subset of [0, 1]K , we will refer to its upset in [0, 1]K as simply its upset. It is immediate
that the upset of a closed and convex subset of [0, 1]K is closed and convex. We define the following
space of Pareto frontiers:
5

Definition 3.3. F is the space of Pareto frontiers in [0, 1]K whose upset is closed and convex.
It is easy to show that F can be equivalently defined as the space of lower Pareto frontiers of
closed and convex subsets of [0, 1]K .1 We will now define a metric on this space. We first recall the
definition of Hausdorff distance induced by the L∞ norm.
Definition 3.4. Let A and B be two subsets of RK . The Hausdorff distance h(A, B) between the
two sets is defined as
h(A, B) = max{sup inf ||x − y||∞ , sup inf ||x − y||∞ }.
x∈A y∈B

y∈B x∈A

The Hausdorff distance defines a metric on the space of non-empty closed subsets of [0, 1]K , and
further, this space is compact and complete in this metric [24]. On the other hand, it only defines a
pseudometric on space of all non-empty subsets of [0, 1]K . Now, a possible straightforward metric
on the space F could be the one defined by the Hausdorff distance. But, as we show in Appendix B,
if K > 2, then a Pareto frontier in F may not be closed, and hence the Hausdorff distance at best
defines a pseudometric on F. Moreover, even this pseudometric is not appropriate for our purposes
as demonstrated by the following example.
Example: Consider a sequence of Pareto frontiers (Vn )n∈N where Vn is the union of the line
segment joining (0, 1) and (1/n, 1/n), and the segment joining (1/n, 1/n) and (1, 0), as depicted in
Figure 2. Then we would like this sequence of frontiers to converge to the Pareto frontier defined
by the singleton set {(0, 0)}, but the Hausdorff distance between Vn and {(0, 0)} doesn’t vanish
as n → ∞. Under the Hausdorff metric, the sequence (Vn )n∈N converges to the union of the line
segment joining (0, 1) and (0, 0), and the segment joining (0, 0) and (1, 0), which is not in F.

(𝟎, 𝟏)

up(V)

Vn

(𝟏/𝒏, 𝟏/𝒏)

(𝟎, 𝟎)

Figure 1: A Pareto frontier V and its
upset up(V) in [0, 1]2 .

(𝟏, 𝟎)

Figure 2: Approximations of (1 − β)V∗ for different β values with corresponding errors

It is thus clear that we need to define a different metric on F. We now proceed to define one with
the desired properties. We define the distance between two Pareto frontiers in F as the Hausdorff
distance between their upsets.2
One direction is clear since a Pareto frontier in F is the lower Pareto frontier of its upset, which is closed and
convex. The other direction follows from the observation that the upset of the lower Pareto frontier of a set is the
upset of the set itself and the upset of a closed and convex set is closed and convex.
2
Since the upsets of the sets in F are compact, the sup and the inf in the definition of the Hausdorff distance can
be replaced by min and max respectively.
1

6

Definition 3.5. For two Pareto frontiers U and V in F, we define the distance d(U, V) between
them as d(U, V) , h(up(U), up(V)).
We can then show that d is a metric on F, and F is both complete and compact in the metric d.
The latter essentially follows from the completeness and compactness of the space of closed subsets
of [0, 1]K in the Hausdorff metric. The proof is presented in Appendix A.
Proposition 3.1. a) d is a metric on F.

b) Let Vn n∈N be a sequence in F. Suppose that supm,k>n d(Vm , Vk ) → 0. Then there exists a
unique V ∈ F such that d(Vn , V) → 0.


c) Let Vn n∈N be a sequence in F. Then there is a subsequence Vnk k∈N and a V ∈ F such that
d(Vnk , V) → 0.
In the proof, it becomes clear that d induces these properties not just on F, but also on the more
general space of Pareto frontiers in [0, 1]K whose upset is closed (though not necessarily convex).
Finally, we end this section by presenting another way of defining the same metric d on F.
Definition 3.6. For two Pareto frontiers V and U in F, define
e(U, V) , inf{ ≥ 0 : ∀ u ∈ U, ∃ v ∈ V s.t. v  u + 1}.

(5)

In other words, e(U, V) is the smallest  ≥ 0 such that U -dominates V (note that e is not a
symmetric distance).3 We can then show the following.
Proposition 3.2. For any two Pareto frontiers V and U in F,
d(U, V) = max(e(U, V), e(V, U))
This means that the distance d between two frontiers V and U is less than or equal to  if both U
and V -dominate each other. This way of defining d is attractive since it does not require defining
upsets of the Pareto frontiers as we do in Definition 3.5. The proof of this equivalence is presented
in Appendix A.

3.2

Dynamic programming operator and the existence of a fixed point.

By scaling and shifting the losses, we assume without loss of generality that rk (a, b) ∈ [0, 1 − β] for
all (a, b, k). Accordingly, the total discounted rewards of the game take values in [0, 1] irrespective
of the time horizon. Now, for any set S ⊆ [0, 1]K , define the following operator Ψ that maps S to a
subset of RK :


Ψ(S) =

max
b∈B

X
a∈A




αa rk (a, b)+βRk (a, b) ; k = 1, · · · , K





: α ∈ ∆(A), R(a, b) ∈ S ∀ a ∈ A, b ∈ B .
(6)

7

(𝟎, 𝟐)

(𝟒, 𝟐)

(𝟐, 𝟐)
𝒖 𝜶

𝟏

𝟏

𝟐

(𝟎, 𝟐)

(𝟐, 𝟎)

(𝟐 𝟏 − 𝜶 , 𝟐𝜶)

(𝟑, 𝟏)

(𝟐𝜶 + 𝟒 𝟏 − 𝜶 , 𝟐 𝟏 − 𝜶 )

𝟐

(𝟐, 𝟎)

(𝟒, 𝟐)

(𝟐, 𝟎)

Figure 4: Construction of the set Ψ(S) where S =
{(0, 0)}, for the game shown in Figure 3.

Figure 3: A game with vector losses.

This operator can be interpreted as follows. Assuming that S is the set of vectors of simultaneous
upper bounds on expected losses that Alice can ensure in GT , Ψ(S) is the set of vectors of simultaneous upper bounds on expected losses that she can ensure in GT +1 . If S is convex then Ψ(S) is
not necessarily convex as we demonstrate in the following example.
Example: Consider the game depicted in Figure 3. Suppose that S = {(0, 0)}, which is convex.
Then for any discount factor β and any (α, 1 − α) where α ∈ [0, 1], one obtains the guarantee:
u(α) = (max(2(1 − α), 2α + 4(1 − α)), max(2α, 2(1 − α))).
This is depicted in Figure 4. Thus, by varying α, we find that the set Ψ(S) is the union of the line
segment joining points (2, 2) and (3, 1) and the segment joining the points (3, 1) and (4, 2). Clearly,
this set is not convex.
Despite the fact that the operator Ψ doesn’t preserve convexity, we can nevertheless show that
if V is a Pareto frontier in F (which means that it is the Pareto frontier of a convex and closed
set), then the Pareto frontier of Ψ(V) is also in F (observe that in the example above, the Pareto
frontier of Ψ({(0, 0)}) is the line segment joining points (2, 2) and (3, 1)). Further, we can also show
that if V ∈ F is the set of vectors of simultaneous upper bounds on expected losses that Alice can
ensure in GT , then in any optimal plan for Alice in GT +1 , the continuation strategy from stage 2
onwards need not depend on her own action in stage 1 (but it could depend on Bob’s action in the
first stage). The proof of this result is presented in Appendix A.
Lemma 3.2. Let V ∈ F. Then:
1. Λ(Ψ(V)) ∈ F.
2. Any point u in Λ(Ψ(V)) is of the form:

u=

max
b∈B

X
a∈A



αa rk (a, b) + βQk (b) ; k = 1, · · · , K .

where Q(b) ∈ V for all b ∈ B.

3
The inf in the definition can be replaced by a min since e(U, V) can be equivalently defined as inf{ ≥ 0 : ∀ u ∈
up(U), ∃ v ∈ up(V) s.t. v  u + 1}, and up(U) and up(V) are compact sets for any U, V ∈ F.

8

We next define the following dynamic programming operator Φ on F.
Definition 3.7. (Dynamic programming operator) For V ∈ F, we define Φ(V) = Λ(Ψ(V)).
From Lemma 3.2, we know that Φ(V) ∈ F whenever V ∈ F. Next, we claim that Φ is a
contraction in the metric d.
Lemma 3.3. e(Φ(U), Φ(V)) ≤ βe(U, V), and hence d(Φ(U), Φ(V)) ≤ βd(U, V).
Finally, we show that the dynamic programming operator has a unique fixed point and starting
from a Pareto frontier in F, the sequence of frontiers obtained by a repeated application of this
operator converges to this point.
Theorem 3.1. Let V ∈ F. Then the sequence (An = Φn (V))n∈N converges in the metric d to a
Pareto frontier V∗ ∈ F, which is the unique fixed point of the operator Φ, i.e., the unique solution
of Φ(V) = V.
We can then show that V∗ is indeed the optimal set V∞ that we are looking for.
Theorem 3.2. V∞ = V∗ .

3.3

Optimal strategies: existence and structure.

For a Pareto frontier V ∈ F, one can define a one-to-one function from some compact parameter set
P to V. Such a function parameterizes the Pareto frontier. We present one such parameterization
that will be used later in our approximation procedure. Define the set
P , ∪K
k=1 {(p1 , · · · , pk−1 , 0, pk , · · · , pK−1 ); pr ∈ [0, 1] for all r = 1, · · · , K − 1}.
P is thus the union of K, K − 1 dimensional faces of the hypercube [0, 1]K , where each face
is obtained by pinning the value along one dimension to 0. For instance for K = 2, we have
P = [0, 1] × {0} ∪ {0} × [0, 1], i.e., the union of the line segment joining (0, 0) and (0, 1), and the
segment joining (0, 0) and (1, 0). Now consider the function F : P × F → RK , where one defines,
F(p, V) = arg min t

(7)

x

s.t. x = t1 + p, t ∈ R,
x  u, u ∈ V.

F(p, V) is essentially the component-wise smallest point of intersection of the line x = t1 + p (for
a fixed p) with the upset of V in [0, 2]K . In R2 , this is simply the family of lines y = x + p0 where
p0 = p2 − p1 , for p0 ∈ [−1, 1] (see Figure 5).

9

y = x + p0
(𝟎, 𝟐)

(𝟎, 𝟏)

V

F (p0 , V)

(𝟏, 𝟎)

(𝟎, 𝟎)

(𝟐, 𝟎)

Figure 5: Parameterization of V.

Then for a given V, the function F(., V) : P → up(V) defines a map such that for every point
u on V, there is a unique p ∈ P that maps only to that point. This is the p such that the line
x = t1 + p intersects V at u (if the line intersects V at two or more points, then one of those points
is dominated by the other(s), which is a contradiction). Note that for some values of p, the line
x = t1 + p may not intersect V, but it will definitely intersect the upset of V in [0, 2]K , which is
why in (7), we optimize over x that dominate u ∈ V, rather than directly optimizing over u ∈ V.
We can now express the dynamic programming operator in the form of such a parametrization.
Assume that V∗ is such that V∗ = Φ(V∗ ). Then for p ∈ P, one can choose α(p) ∈ ∆(A) and
q(b, p) ∈ P for each b ∈ B such that for k ∈ {1, · · · , K},
Fk (p, V∗ ) = max{
b∈B

X

αa (p)rk (a, b) + βFk (q(b, p), V∗ )}.

(8)

a∈A

Then we have the following result.
Theorem 3.3. For any p1 ∈ P, the upper bound F(p1 , V∗ ) ∈ V∗ on losses is guaranteed by Alice
in the infinite horizon game by first choosing action a1 ∈ A with probability αa1 (p1 ). Then if Bob
chooses an action b1 ∈ B, the optimal guarantees to choose from the second step onwards are then
βF(p2 , V∗ ) in βV∗ , where p2 = q(b1 , p1 ), which can be guaranteed by Alice by choosing action
a2 ∈ A with probability αa2 (p2 ), and so on.
This implies that P can be thought of as a compact state space for the strategy. Each state is
associated with an immediate optimal randomized action and a transition rule that depends on the
observed action of Bob. In order to attain a point in V∗ , Alice starts with the corresponding state,
plays the associated randomized action, transitions into another state depending on Bob’s observed
action as dictated by the rule, plays the randomized action associated with the new state and so on.
In particular, the strategy does not depend on the past actions of Alice and it depends on the past
actions of Bob only through this information state that Alice keeps track of. It is interesting to note
that unlike in stochastic games or Markov decision processes (MDPs) [34], the state transitions
are not exogenously defined but they are endogenously specified by the dynamic programming
operator.

10

4

Approximation.

In general, except for simple examples (we will see such an example in Section 6.3.2), it is difficult
to analytically compute V∗ and {(α(p), q(b, p)) : p ∈ P} that satisfies (8) by simply using the
fixed point relation. Hence, we now propose an approximate dynamic programming procedure to
approximate the optimal Pareto frontier and devise approximately optimal strategies. In order
to do so, we need to first define an approximation of any Pareto frontier. Consider the following
approximation scheme for a Pareto frontier V ∈ F. For a fixed positive integer N , define the set
1 2
N −1
, ,··· ,
, 1} ∀ r = 1, · · · , K − 1}.
N N
N
(9)
PN is thus obtained by approximating each of the K, K − 1 dimensional faces in P by a grid of
points. The number of points in this set is
PN = ∪K
k=1 {(p1 , · · · , pk−1 , 0, pk , · · · , pK−1 ); pr ∈ {0,

H(K, N ) , K(N + 1)K−1 − (K − 1).
Define the approximation operator to be
 


ΓN (V) = Λ ch F(p, V) : p ∈ PN
,

(10)

(11)

where F(p, V) was defined in (7). Here ch denotes the closed convex hull of a set. Thus ΓN (V) ∈ F
is the Lower Pareto frontier of a convex polytope, and it has at most H(K, N ) vertices, where each
vertex is the point of intersection of the line x = t1 + p with the upset of V for some p ∈ PN . We
can then show the following approximation guarantee.
Proposition 4.1. Consider a V ∈ F. Then
e(ΓN (V), V) = 0 and e(V, ΓN (V)) ≤
and hence
d(V, ΓN (V)) ≤

1
,
N

1
.
N

Next, we can express the compound operator ΓN ◦ Φ via a set of explicit optimization problems
as in (7), that only take V as input:
F(p, Φ(V)) = arg min t

(12)

x

s.t. x = t1 + p, t ∈ R,
X
x
αa r(a, b) + βQ(b) ∀ b ∈ B,
a∈A

α ∈ ∆(A), Q(b) ∈ V ∀ b ∈ B.
If V ∈ F is the lower Pareto frontier of a convex polytope, then this is a linear program, and
further ΓN ◦ Φ(V) is also the lower Pareto frontier of a convex polytope. We then we have the
following result.
11

Proposition 4.2. Let G0 = {0} and let Gn = (ΓN ◦ Φ)n (G0 ). Then
1
e(Gn , V ) ≤ β and e(V , Gn ) ≤
N
∗

∗

n

And thus
1
d(V , Gn ) ≤
N
∗



1 − βn
1−β





1 − βn
1−β



+ βn.

(13)

+ βn.

Hence for any , there is a pair (N, n) such that d(V∗ , Gn ) ≤ . This result implies an iterative
procedure for approximating V∗ by successively applying the compound operator ΓN ◦ Φ to G0 ,
by solving the above linear program at each step. Since Gn is a lower Pareto frontier of a convex
polytope, with at most H(K, N ) vertices for each n, the size of the linear program remains the
same throughout. More details on solving this linear program can be found in Appendix C.
The fact that e(Gn , V∗ ) ≤ β n implies that Gn β n -dominates V∗ for all n, and thus the optimal
upper bounds in V∗ cannot be larger than in Gn + β n 1. Thus as n gets larger, the set Gn + β n 1
approaches V∗ “from above”, and in the limit, ends up within a 1/(N (1 − β)) distance of V∗ .

4.1

Extracting an approximately optimal strategy.

From Gn , one can also extract an approximately optimal strategy πn in the infinite horizon game.
Suppose α∗ (p) and Q∗ (b, p) for b ∈ B are the optimal values that solve the program (12) to
compute F(p, Φ(Gn )) for different p ∈ PN . Then these define an approximately optimal strategy
in the following class:
Definition 4.1. A H(K, N )−mode stationary strategy π is a mapping from each p ∈ PN to the
pair
1. α(p) ∈ ∆(A), and


2. q1 (b, p), · · · , qK (b, p), z(b, p) , where for all b ∈ B, qk (b, p) ∈ PN for all k = 1, · · · , K
and z(b, p) ∈ ∆K .
Here, ∆K is the unit simplex in RK . The interpretation is as follows. One starts with some
initial mode, i.e., a value of p ∈ PN . Then at any step, if the current mode is p, then Alice first
chooses action a ∈ A with probability αa (p). Then if Bob plays action b ∈ B, Alice samples the
new mode to be qk (b, p) with probability zk (b, p) for each k, and after having sampled a new mode,
plays accordingly thereafter.


∗
Now, α (p) defines α(p) in πn , and q1 (b, p), · · · , qK (b, p), z(b, p) are defined such that they
satisfy
Q∗ (b, p) =

K
X

zk0 (b, p)F(qk0 (b, p), Gn ).

(14)

k0 =1

The interpretation is as follows. If V is the lower Pareto frontier of a convex polytope with each
vertex lying on the line x = t1 + p for some p ∈ PN , Q∗ (b, p) for each b ∈ B that results from
12

solving (12) will lie on one of the faces of this Pareto frontier. Thus Q∗ (b, p) can be expressed as
a convex combination of (at most K) extreme points of the face as expressed in (14).
Let Vπn be the corresponding Pareto frontier that is attained by the strategy πn (each point on
this frontier is guaranteed by choosing different possible initial randomizations over the H(K, N )
modes). Simply from the definition of V∗ as the optimal frontier, we know that Vπn dominates V∗ ,
i.e., e(Vπn , V∗ ) = 0. But we can also show the following.
Proposition 4.3.
d(Vπn , V∗ ) ≤

1
N



1 − βn
1−β



+ 2β n +

1
N




2 − β n − β n+1
.
(1 − β)2

(15)

Thus an approximately optimal strategy can be obtained by choosing an appropriate (N, n).
Remark: The procedure to approximate the frontier and extract an approximately optimal
strategy illustrates that our characterization of the minmax optimal strategy via the fixed point of
a dynamic programming operator opens up the possibility of using several approximate dynamic
programming procedures; for instance, see Chapter 6 in [9]. Here we have not tried to determine a
computation procedure that achieves the optimal error-complexity tradeoff. For a fixed (N, n), in
order to approximate the optimal frontier, the procedure needs to solve nH(K, N ) linear programs
to give the corresponding error bound in Proposition 4.2. In our implementation described in
Appendix C, each linear program is composed of mH(K, N ) + l + 1 variables and Km + K + 1
constraints (recall that H(K, N ) is polynomial in N for a fixed K).
One can focus on two terms in the approximation error separately: the first term is the quan1
tization error which is bounded by N (1−β)
and second is the iteration error which is bounded by
n
β . The second term is relatively benign since it decays exponentially in n. The first term requires
1
N = (1−β)
to achieve an error of , which grows rapidly as β gets closer to 1. For finding an
1
approximately optimal strategy, the scaling is like (1−β)
2  , which grows even faster. But for fixed
values of β not too close to 1, the computation isn’t prohibitive and this is precisely the case where
other no-regret algorithms fare poorly. Further, this computation can be done offline, and needs to
be performed only once. The resulting approximately optimal strategy requires a bounded memory
1
(O(log(H(K, (1−β)
2 )) bits) and is very simple to implement via a look-up table.

5

Application 1: Zero-sum repeated games with lack of information on one side.

One of the most celebrated and well studied models of dynamic games with incomplete information
is a model introduced by Aumann and Maschler [6] of zero-sum repeated games with incomplete
information on one side. It is described as follows.
There are K two person zero-sum games G1 , · · · , GK , each with m actions, A = {1, · · · , m}
for player 1, who is the minimizer (Alice), and n actions B = {1, · · · , n} for player 2, who is the
maximizer (Bob). Let the loss corresponding to actions a and b of Alice and Bob respectively be
denoted by rk (a, b) in game Gk .
∞
We define the
P game G as follows. One of the K games Gk is chosen by nature with probability
pk , such that k pk = 1. This distribution is known to both the players but the actual choice of

13

the game is informed to Bob and not to Alice. Let the chosen (random) game be denoted by G.
Then this game G is played infinitely often in stages t = 1, · · · , ∞. At each stage t, Alice and Bob
play their actions simultaneously. The payoff that is incurred by the players is not observed by
Alice at any stage (if she did, the game could be identified immediately), but she observes Bob’s
actions. Intuitively, Bob’s goal is thus to try to maximize Alice’s loss while utilizing his information
efficiently, since such utilization leads to information leakage, while Alice’s goal is to minimize her
loss while utilizing any leaked information.
An adaptive randomized strategy (also called a behavioral strategy) πA for Alice specifies for
each time t, a mapping from her set of observations till time t, i.e. HtA = (a1 , b1 , · · · , at−1 , bt−1 ),
to ∆(A). A behavioral strategy πB for Bob specifies for each time t a mapping from his set of
observations till time t and the chosen game G, i.e., HtB = (G, a1 , b1 , · · · , at−1 , bt−1 ), to ∆(B). We
k ; k = 1, · · · , K), where π k is his strategy
will express the behavioral strategy πB of Bob as πB = (πB
B
conditioned on the event {G = Gk }.
We now formally specify the objectives of the two players in G∞ . For a discount factor β ∈ (0, 1)
and for a choice of strategies πA and πB of the two players, the ex-ante expected loss is given by
R(πA , πB ) = EπA ,πB ,G

X
∞

β

t−1


rG (at , bt ) =

t=1

K
X

pk EπA ,πk

X
∞

B

β

t−1


rk (at , bt ) .

(16)

t=1

k=1

Alice’s objective is to minimize this payoff while Bob’s objective is to maximize it. The minmax or
the upper value of the game is given by
V = min
πA

K
X

pk max EπA ,πk

k=1

X
∞

B

k
πB

β

t−1


rk (at , bt ) .

(17)

t=1

The minimizing strategy in the outer minimization problem is the minmax optimal strategy for
Alice; we will simply call it her optimal strategy. Similarly, the maxmin or the lower value of the
game is given by
V=

max

min

k ;k=1,··· ,K) πA
(πB

X
K

pk EπA ,πk

X
∞

B

β

t−1


rk (at , bt ) .

(18)

t=1

k=1

The optimal strategy for Bob is similarly defined as his maxmin strategy, i.e. the maximizing
strategy in the outer maximization problem. In general, we have that V ≥ V, but in this case one
can show that a minmax theorem holds and V = V [6, 37, 41, 31].
Characterizing the maxmin optimal strategy for Bob: To characterize and compute
the maxmin strategy for Bob, one can use a dynamic programming approach that exploits the
structural relationship between the original game and the game after one stage has elapsed [37, 41].
Suppose V (p) is a function that assigns to every prior probability distribution p over the game
G, the maxmin value of the associated infinitely repeated game. Then it is easy to show [37, 41]
that the maxmin value as a function of the prior p is the fixed point of the following contractive
dynamic programming operator defined on the function V : ∆K → R (here ∆K is the unit simplex

14

in RK ) :
T(V )(p) =

max

min

k ∈∆B;k=1,··· ,K) qA ∈∆A
(qB

K
X

pk Eqk ,qA [rk (a, b)]
B

k=1



K
k (b)
X

p k qB
k
; k = 1, · · · , K .
+
β(
pk qB (b))V
PK
k (b)
p
q
k
k=1
B
b∈B
k=1
X

This operator can be understood as follows. Notice that in the first stage, the probability distributions over Bob’s actions chosen by him for each of the K games as a part of his strategy πB , makes
his realized action a (potentially) informative signal of the true game chosen by nature. Since
Alice can be assumed to know this strategy in the computation of the maxmin, she can perform
a Bayesian update of her belief about the chosen game after having observed Bob’s action. Thus
once the randomization of Bob in the first stage is fixed, there is a one-stage expected loss that is
minimized by Alice, and then every realized action of Bob results in a new game with an associated
maxmin value, that is identical in structure to the original game, except that the original prior is
replaced with the posterior distribution conditional on that action (note that the state transitions
in the space of posteriors are independent of Alice’s actions). Bob thus chooses a randomization
for each of the K games that maximizes the sum of these two values. Consistency then requires
that the function V (p) has to be the fixed point of this resulting operator. It also follows that the
optimal strategy for Bob is a stationary strategy that depends only on the posterior pt at stage t.
Characterizing the minmax optimal strategy for Alice: Now it turns out that a similar
approach cannot be used to compute and characterize the minmax optimal strategy for Alice, the
uninformed player. The problem is that in order to perform the Bayesian update as a part of
her strategy πA , Alice needs to know Bob’s strategy πB , which means that πA presupposes the
knowledge of πB , which contradicts the fact that the maxmin strategy is ‘universal’: it guarantees
that her loss is no more than V irrespective of the strategy chosen by Bob. Even if Bob’s optimal
strategy is unique, the best response strategy of Alice that computes the posterior updates at each
stage and plays optimally accordingly is vulnerable to bluffing by Bob. Thus the optimal strategy
of Alice cannot rely on the computation of these posterior distributions and must instead depend in
some form on Bob’s actions and the corresponding losses incurred in the different possible choices
of games.
To the best of our knowledge, the exact computation or even approximation of Alice’s optimal
strategy has been an open problem. Structurally, all that is known (see Corollary 3.25 in [37]) about
the optimal strategy is that Alice’s decision at stage t doesn’t depend on her own past actions, but
can depend on potentially all of Bob’s actions till time t. This also suggests the possibility that
any dynamic programming based procedure that may be developed to compute this strategy will
have a non-compact state space and thus suffer from the curse of dimensionality, i.e., the state may
include the entire history of actions.
We propose the following key step that resolves this problem. Instead of computing the upper
value V corresponding to the prior distribution p, suppose that one computes the following set:
W=


max E
k
πB

X
∞
t=1




β t−1 rk (at , bt ) ; k = 1, · · · , K : πA ∈ ΠA .

(19)

This is the set of upper bounds on losses that Alice can simultaneously achieve on the K components
of the vector of the long term discounted losses, by playing all the possible strategies in ΠA . In fact,
15

one need not compute the entire set W, but just its lower Pareto frontier Λ(W). If we determine
this set, then one can simply choose a point r(p) ∈ Λ(W) such that
r(p) = arg min

K
X

pk rk .

(20)

r∈Λ(W) k=1

The corresponding strategy of Alice that results in the simultaneous guarantee r is then the optimal
strategy in the original game. Thus we are interested in characterizing the set V∗ = Λ(W). But
this is exactly the set we characterized using the set-valued dynamic programming approach.
Using our approach, first, we immediately deduce the known fact that the optimal strategy of
Alice doesn’t depend on her own past actions (Theorem 3.3). Second, we also obtain a previously
unknown insight into its structure: Alice’s optimal strategy is stationary relative to a compact
state space as described in Theorem 3.3. This state space can be compared to the compact state
space of Bob’s optimal strategy, which is the space of probability distributions on the K games.
It is interesting to note that the state transitions for Bob’s strategy are exogenously determined
by the Bayesian updating of the posterior, whereas the state transitions for Alice’s strategy are
endogenously determined by the dynamic programming operator (as we had remarked earlier in
Section 3.3). Third, the compactness of the state space opens up the possibility to approximate
Alice’s optimal strategy, as we have demonstrated in Section 4. To the best of our knowledge, this
is the first known approximation procedure for the this problem.
Note that we solve a harder problem than the one we set out to solve, since instead of computing the minmax value corresponding to one prior p, in effect we are trying to simultaneously
compute the minmax values corresponding to all the possible priors. But it turns out that this
harder objective makes this problem suddenly become amenable to a dynamic programming based
approach. This should not be too surprising, since as we have seen for the case of the informed
player, in order to solve for the lower value corresponding to a prior p and to compute the optimal
strategy, one needs to simultaneously solve for games starting from all possible priors p ∈ ∆K .

6

Application 2: Regret minimization in repeated games.

The regret minimization paradigm models a repeated decision-making problem in an uncertain
environment as a repeated game between the decision-making agent and an adversary. The key
notion is that of “regret”, defined as the difference between the loss incurred by the decision maker’s
choice of actions, and the loss incurred by the best fixed action that could have been chosen in
hindsight against the sequence of actions chosen by the environment. The decision maker’s goal in
this game is to design an adaptive and possibly randomized strategy that minimizes the expected
regret in the worst case over all the possible sequences of actions of the environment. Since its
inception by Hannan in the 1950s [23], this formulation of an online decision-making problem under
uncertainty has been widely popular both in theory and practice. In this setting, several no-regret
√
algorithms exist, which ensure that if the decision-making horizon is N , the regret scales like O( N )
with high probability irrespective of the sequence of actions chosen by the adversary. Hence the
time-averaged regret (i.e., the cesaro sum) asymptotically vanishes in an infinitely repeated game,
not just in expectation, but with probability 1.
Blackwell [11] had noticed early on that his approachability framework can be used to obtain
no-regret strategies as formulated by Hannan by transforming the original repeated game into a
repeated game with vector-valued losses. In this new game, the number of vector components is
16

the number of actions available to the decision-maker, where each component keeps track of the
additional loss incurred by the strategy relative to the loss incurred if the corresponding action
was always chosen in the past. The goal of regret minimization in the original game now translates to the goal of minimizing the maximum worst-case expected loss across all the components
in this vector-valued game. Approachability theory immediately shows that the negative orthant
is approachable in this game, thus resulting in yet another no-regret algorithm. Stronger connections of the approachability framework with regret minimization and other learning problems like
calibration have subsequently been shown [1, 33].
In discounted repeated games, the loss criterion is the weighted sum of per-stage losses, with
the loss at stage t ≥ 1 weighted by β t−1 , where β ∈ (0, 1) is called the discount factor. Such
discounting is common in literature and is natural in practice, where minimizing current losses
is more important than √
the ones in the future. Several known no-regret algorithms guarantee an
expected regret of O(1/ 1 − β) as β → 1 in an infinitely repeated game, but for a given discount
factor β, their performance can be far from optimal. Overall, except for specific instances, exact
regret optimality has been difficult to achieve, and there is no known systematic procedure to
compute even approximately optimal algorithms.
In this scenario, we can couple Blackwell’s transformation with our dynamic programming based
approach to characterize the Pareto frontier of minimal regret relative to the different actions. Apart
from providing new insights into the structure of the regret optimal strategy, our approximation
scheme described in Section 4 allows us to compute an approximately regret optimal strategy.
We will formally present the regret minimization problem and its transformation into a vector
valued game, to which our approach can then be readily applied. We will then demonstrate the
applicability of our approximation scheme to the problem of prediction using expert advice with
binary losses and two experts. Since this is an extensively studied area, we begin by discussing
some of the relevant literature so as to provide some context for our contribution.

6.1

Related literature.

The first study of regret minimization in repeated games dates back to the pioneering work of
Hannan [23], who introduced the notion of regret optimality in repeated games and proposed
the earliest known no-regret algorithm. Since then, numerous other such algorithms have been
proposed, particularly for the problem of prediction using expert advice, see [29, 40, 14, 21], one
particularly well-known class being the multiplicative weights update class of algorithms. Other
settings with limited feedback have been considered, most notably the multi-armed bandit setting
[5, 13]. Stronger notions of regret such as internal regret, have also been studied [19, 16, 12, 38].
Regret minimization with non-uniformly weighted losses, of which the discounted loss is a special
case, has also been considered before [15, 17, 33]. While the average regret goes to zero if the weights
satisfy a non-summability condition, lower bounds exist ([15], Thm 2.7) that show that the optimal
regret is bounded away from 0 if the weights are summable, which is the case
√ with discounting.
Natural extensions of no-regret algorithms incur a cumulative regret of O(1/ 1 − β) (and hence
√
√
an average regret of O(1/ 1 − β)(1 − β) = O( 1 − β)) in this case; for instance see Thm 2.8 in
[15] and Prop. 2.22 in [33]. [17] derives better bounds for the case where future losses are given a
higher weight that current ones.
The results on exact regret minimization are few. In an early work, Cover [18] gave the optimal
algorithm for the problem of prediction using expert advice over any finite horizon T , for the
case of 2 experts, and where the losses are {0, 1}. [22] recently extended the result to the case
17

of 3 experts for both the finite horizon and geometrically distributed random horizon problems.
Although a geometric time horizon model seems to be related to the infinite horizon model with
discounted losses, the two problem formulations define regret differently, and thus lead to different
optimal regrets. We discuss this in Section 6.3.1. [2] considered a related problem, where a gambler
places bets from a finite budget repeatedly on a fixed menu of events, the outcomes of which
are adversarially chosen from {0, 1} (you win or you lose), and characterized the minmax optimal
strategies for the gambler and the adversary. [30] considered a similar repeated decision-making
problem where an adversary is restricted to pick loss vectors (i.e., a loss for each action of the
decision-maker in a stage) from a set of basis vectors, and characterized the minmax optimal
strategy for the decision-maker under both, a fixed and an unknown horizon. Most of the approaches
in these works are specific to their settings, and exploit the assumptions on the structure of the
loss vectors. But if the loss vectors are arbitrary, these approaches are difficult to generalize and
indeed it is recognized that characterizing the optimal regret and algorithm is difficult; cf. [30].4

6.2

The regret minimization problem and its transformation.

Let G be a two player game with m actions A = {1, . . . , m} for player 1, who is assumed to be
the minimizer and who we will call Alice (the decision-maker), and n actions B = {1, . . . , n} for
player 2, who is the adversary and who we will call Bob, in keeping with the previous notation.
For each pair of actions a ∈ A and b ∈ B, the corresponding loss for Alice is l(a, b) ∈ R. The losses
for different pairs of actions are known to Alice. The game G is played repeatedly for T stages
t = 1, 2, · · · , T . In each stage, both Alice and Bob simultaneously pick their actions at ∈ A and
bt ∈ B and Alice incurs the corresponding loss l(at , bt ). The loss of the repeated game is defined
P
to be the total discounted loss given by Tt=1 β t−1 l(at , bt ), where β ∈ (0, 1). We define the total
discounted regret of Alice as:
T
X
t=1

β

t−1

l(at , bt ) − min
a∈A

T
X

β t−1 l(a, bt ),

(21)

t=1

which is the difference between her actual discounted loss, and the loss corresponding to the single
best action that could have been chosen against the sequence of actions chosen by Bob in hindsight.
An adaptive randomized strategy πA for Alice specifies for each stage t, a mapping from the set
of observations till stage t, i.e., Ht = (a1 , b1 , · · · , at−1 , bt−1 ), to a probability distribution on the
action set A, denoted by ∆(A). Let ΠA be the set of all such strategies of Alice. The adversary
Bob is assumed to choose a deterministic oblivious strategy, i.e., his choice is simply a sequence of
actions πB = (b1 , b2 , b3 , · · · , bT ) chosen before the start of the game. Let ΠB be the set of all such
sequences.5 We would like to compute the worst case or minmax expected discounted regret which
4

All of the examples we discuss are of games with finite action spaces, which is the setting that we are concerned
with. But there are many works that consider exact minmax optimality in repeated games with general action sets,
with specific types of loss functions; see [26, 7, 27] and references therein.
5
Having an oblivious adversary is a standard assumption in regret-minimization literature [5, 13, 15]. This makes
sense when “nature” is modeled as an adversary in an application, which would be the case for instance in weather
forecasting. Also see Chapter 3 in [13] for a discussion of different adversary models and their implications on different
definitions of regret.

18

is defined as:
min

max EπA ,πB

X
T

πA ∈ΠA πB ∈ΠB

β

t−1


= min

max EπA ,πB max

πA ∈ΠA πB ∈ΠB

l(at , bt ) − min
a∈A

t=1

X
T

a∈A

β

t−1

t=1

T
X

β

t−1


l(a, bt )

t=1

l(at , bt ) −

T
X

β

t−1


l(a, bt ) ,

(22)

t=1

and the strategy for Alice that guarantees this value. Since Bob’s strategy πB is deterministic
and oblivious, the expectation in (22) is effectively only over the randomness in Alice’s strategy,
and moreover the second term does not depend on Alice’s strategy. Thus we can exchange the
expectation and the inner maximization and equivalently write (22) as:
min

max max EπA ,πB

X
T

πA ∈ΠA πB ∈ΠB a∈A

β

t−1

t=1


(l(at , bt ) − l(a, bt )) .

(23)

This quantity is called the pseudo-regret in regret minimization literature (see Chapter 3 in [13]).
The expected regret is equivalent to the pseudo-regret only when the adversary’s strategy is deterministic and oblivious; in general if the adversary’s strategy is randomized and adaptive, then the
pseudo-regret is smaller than the expected regret.
In order to address this objective, it is convenient to define a vector-valued game G, in which,
for a pair of actions a ∈ A and b ∈ B, the vector of losses is r(a, b) with m components (recall that
|A| = m), where
rk (a, b) = l(a, b) − l(k, b)
(24)
for k = 1, · · · , m. rk (a, b) is the single-stage additional loss that Alice bears by choosing action a
instead of action k, when Bob chooses b: the so called “single-stage regret” with respect to action k.
For a choice of strategies πA ∈ ΠA and πB ∈ ΠB of the two players, the expected loss on component
k in this vector-valued repeated game over horizon T is given by
RkT (πA , πB )

= E πA

X
T

β

t−1


rk (at , bt ) ,

(25)

t=1

where the expectation is over the randomness in Alice’s strategy. Now observe that by playing a
fixed strategy πA ∈ ΠA , irrespective of the strategy chosen by Bob, Alice guarantees that the total
k ). Suppose that we determine
expected loss on component k is no more than maxπk ∈ΠB RkT (πA , πB
B
the set of all simultaneous upper bounds that correspond to all the strategies πA ∈ ΠA , defined as:



T
T
k
W ,
max Rk (πA , πB )
: πA ∈ ΠA .
(26)
k ∈Π
πB
B

k=1,··· ,m

Then it is clear that the minmax optimal regret can be written as:
min

max max EπA

πA ∈ΠA πB ∈ΠB a∈A

X
T
t=1

β

t−1


(l(at , bt ) − l(a, bt )) = min max xk .
x∈WT

k

In fact, it suffices to characterize the lower Pareto frontier of the set WT , i.e., Λ(WT ), and the
strategies that achieve this frontier, since all other points are strictly sub-optimal. In particular, we
19

are interested in Λ(W∞ ). Here we remark that it may seem curious that instead of simply focusing
on computing the minmax optimal regret, we have expanded our objective to characterizing the
entire Pareto frontier of minimal regret relative to all actions. But this expanded objective is
precisely what opens up this problem to a dynamic programming based approach. One way to
see this is to realize that in order to achieve the minimal optimal regret, it is necessary to know
the optimal strategies that focus on reducing regret relative to certain actions more than others,
since these strategies will form the optimal response plans for the decision-maker as the profile
of accumulated regret relative to the different actions changes. We mention here that the idea
of characterizing the Pareto Frontier of all achievable regrets with respect to different actions has
been explored by [25], but this was in the specific context of prediction with expert advice with 2
experts and {0, 1}−losses, and for the finite time horizon problem.

Now we can show that the set Λ(W∞ ) (and Λ(WT ), in general) is exactly what we are able to
characterize and approximate using our set-valued dynamic programming approach. To see this,
notice that the only difference in assumptions is the set of strategies the adversary can use in the
two formulations. Recall that when we defined the dynamic programming operator for our vectorvalued repeated game, we assumed that Bob is allowed to choose any adaptive strategy (that could
in particular depend on the actions chosen by Alice). Thus our results are directly applicable to the
problem of minimizing pseudo-regret when the adversary is allowed to use a general strategy. But
we need to argue that they are also applicable to the problem of minimizing pseudo-regret/expected
regret in the case where Bob is restricted to using an oblivious deterministic strategy.
We do so by arguing that even if we restrict Bob to an oblivious deterministic strategy in
our original vector-valued repeated game, the set of minimal upper bounds on losses that Alice
can guarantee is still V∗ , the fixed point of our operator. First, recall that Bob’s best response
to Alice’s optimal strategy that achieves different points on the frontier V∗ is deterministic and
oblivious (offline). This is because Alice does not take into account her own actions to determine
the information state transitions (Theorem 3.3). In fact, if Alice is restricted to use strategies that
do not depend on her own actions chosen in the past, then the best response to such strategy
is always an offline deterministic strategy, and hence the minimal achievable frontier if Bob is
restricted to use offline deterministic strategies is V∗ . So all that we need to verify is that Alice
does not gain by using strategies that depend on her own past actions, when Bob is restricted to
using only offline deterministic strategies.

To see this is indeed the case, suppose that VT is the set of minimal guarantees that Alice can
achieve by using general randomized adaptive strategies in GT , assuming that Bob is restricted to
using deterministic offline strategies. Then in GT +1 , Alice’s strategy is a choice of a distribution over
her actions, α, and a mapping from the realized actions (a, b) to some continuation (randomized,
adaptive) strategy π(a, b) ∈ ΠA . But since Bob’s responses that maximize the losses on the different
components cannot depend on the realization of Alice’s action a, and can only depend on α, his best
responses from time 2 onwards would effectively be against the strategy π 0 (b) of Alice that chooses
the strategy π(a, b) with probability αa for each action a. Thus Alice could as well have chosen the
continuation strategy independently of her chosen action a. And this strategy ought to guarantee
a point in VT , since all other strategies that guarantee points outside VT are strictly-suboptimal.
Thus the guarantees that Alice can achieve in GT +1 is given by the set:




X 

T +1
V =Λ
max
αa rk (a, b) + βQk (b) ; k = 1, · · · , K : α ∈ ∆(A), Q(b) ∈ V
∀b ∈ B
.
T

b∈B

a∈A

20

But this is exactly the dynamic programming operator in Definition 3.7. Hence we can conclude
that V∗ is indeed the set of minimal guarantees, even if Bob is restricted to using deterministic
offline strategies.

6.3

Example: Combining expert advice.

Consider the following model of combining expert advice. There are two experts who give Alice
recommendation for a decision-making task: say predicting which route will be the fastest to go
to work the next day. Each day Alice decides to act on the recommendation made by one of the
experts. The experts’ recommendations may be correct or wrong, and if Alice acts on an incorrect
recommendation, she bears a loss of 1. Otherwise she does not incur any loss. Each day, exactly
one expert is correct and the other is wrong.6 This model can be represented by the matrix shown
in Figure 6. The rows correspond to the choice made by Alice and the columns correspond to the
two different possibilities for the correct expect on each day. The matrix of single-stage regrets is
shown in Figure 7.
𝟏

𝟐

𝟏

Expert 1

𝟏

𝟎

Expert 1

Expert 2

𝟎

𝟏

Expert 2

Figure 6: Possible loss scenarios

𝟐

(𝟎, 𝟏) (𝟎, −𝟏)
(−𝟏, 𝟎) (𝟏, 𝟎)

Figure 7: Single-stage regret w.r.t. Expert 1
& 2.

1.0

1.3

(N, n)

1.2

= 0.5

(40, 8)

1.1

= 0.6

(50, 11)

1.0

0.8

0.6

= 0.7
0.4

(67, 17)

= 0.8
= 0.9
= 0.95

0.2

0.9

(101, 28)

0.8

(201, 66)

0.7

(400, 149)

0.6
0.0
0.0

0.2

0.4

0.6

0.8

0.5

1.0

0.5

0.6

0.7

0.8

0.9

0.95

β

Figure 8: Approximations of the optimal
frontier (1 − β)V∗ (β) for different β values
and the associated (N, n). (N, n) values in
each case are chosen so that the approximation error (Proposition 4.2) is less than 0.06.
n is chosen so that β n /(1 − β) ≤ 0.01.

Figure 9: Upper bounds on the optimal expected regret plotted as a function of the discount factor β.

6

It is not expected to be optimal for the adversary trying to maximize Alice’s regret to have both the experts be
correct or both be wrong. Hence these actions are omitted.

21

In Figure 8, the computed approximately optimal Pareto frontiers of regret for a range of values
of β are shown. (N, n) is chosen in each case so that the error in the approximation of (1−β)V∗ (β) is
at most 0.06. Further, n is chosen in each case so that β n /(1 − β) ≤ 0.01, and hence Proposition 4.2
guarantees that 0.01 added to the approximations of optimal regret for each β result in upper bounds
on the optimal regret. These upper bounds are plotted in Figure 9.
6.3.1

Comparison with other algorithms.

In this section, we compare the performance of approximately optimal algorithms derived from
our approach to two known algorithms for the problem of prediction with expert advice. We will
consider discount factors β = 0.8 and 0.9, and K = 2 and 3 experts.7
The first algorithm we consider is the well known the exponentially weighted average forecaster,
also known as “Hedge”. In this algorithm, if Lt (i) is the cumulative loss of expert i till time t, then
the probability of choosing expert i at time t + 1 is
pi (t + 1) ∝ exp(−ηLt (i)),
p
where η is a parameter. In the undiscounted problem, choosing η = 8 log K/T when the time
p
horizon T is known attains an upper bound of T log K/2 on the expected cumulative regret (Thm.
2.2, [15]). In a certain sense, this is shown to be asymptotically optimal in K and T for general loss
function taking values in [0, 1] (Thm. 3.7, [15]). In our implementation, we use discounted cumulap
tive losses in this algorithm, and choose η = 8 log K(1 − β 2 ). This resulting algorithm achieves an
p
p
upper bound of log K/2(1 − β 2 ) = log K/(2(1 − β)(1 + β)) on the expected discounted regret
in the infinitely repeated game (see proof of Thm. 2.2, and Thm. 2.8 in [15]).
Next, we consider the optimal algorithms given by Gravin, Peres and Sivan [22] (which we
will refer to as GPS) for the experts problem with a geometrically distributed time horizon with
K = 2 and 3 experts. In this model, at each stage, the game ends with a probability 1 − β
and continues with probability β. This is essentially the same as our model of discounted losses,
where the discount factor is interpreted as the probability of continuation at each stage. But the
difference between that formulation and our formulation is in the definition of regret. In their
formulation, the loss of the decision-maker is compared to the expected loss of the best expert
in the realized time horizon (where the expectation is over the randomness in the time horizon),
P
i.e., to ET [mini=1,2 Tt=1 lt (i)], where lt (i) is the loss of expert i at time t. On the other hand, in
our formulation, the loss of the decision-maker is compared to the expert with the lowest expected
P
P
t−1 l (i). Naturally, the optimal regret in their
loss, i.e., to mini=1,2 ET [ Tt=1 lt (i)] = mini=1,2 ∞
t
t=1 β
formulation is at least as high as the optimal regret in our formulation, and in fact it turns out to
be strictly higher. For example, for K = 2 and β = 0.9, the optimal regret in their formulation
is ≈ 1.147,8 while in our formulation, the optimal regret in this case is at most ≈ 0.9338 (see
Figure 9). Further, it is clear that their optimal strategy gives the same guarantee for our definition of regret as the optimal regret in their definition, i.e., for instance, for β = 0.9, their strategy
will guarantee an expected regret of at most ≈ 1.147 according to our definition. Note that in the
7

The code for all our numerical experiments can be found at https://github.com/vijaykamble/
vector-repeated-games.
8
The optimal regret for [22]’s formulation is √ 1 2 . The expression in [22] is off by a factor of β since they
2

1−β

discount the first period by β (i.e., the game could end before the first stage begins), whereas we discount it by 1.

22

context where discounting captures the temporal change in the present value of money, our formulation of regret is the natural one. The GPS algorithms for K = 2 and 3 are described in Appendix D.
Results for K=2.
We first consider K = 2 experts. We compare the performance of
our approximately optimal strategy with the performance of GPS and Hedge against 3 different
adversaries:
1. Adversary A: This adversary gives a loss of 1 to one expert (and 0 to the other) uniformly at
random. In the geometrically distributed time horizon model with regret as defined in [22],
this has been shown to be the maxmin optimal adversary.
√
2. Adversary B: This adversary chooses a Bernoulli(1/2 − 1 − β) loss for expert 1 and a
Bernoulli(1/2) loss for expert 2.9
3. Adversary C: In this adversary’s strategy, the probability that expert 1 incurs a loss (and
expert 2 doesn’t) at time t is 0.91/t if t is odd, and 0.9t if t is even.

Figures 11 and 10 compare the expected regret incurred by Hedge and GPS to the expected
regret incurred by our approximately optimal strategies for β = 0.8 and 0.9. For β = 0.8 we
computed a 203−mode (H(2, 101)) strategy and a 21−mode (H(2, 10)) strategy (n = 28 in both
cases). For β = 0.9 we computed a 403−mode (H(2, 201)) strategy and a 41−mode (H(2, 20))
strategy (n = 66 in both cases). The expected regret is estimated in each case by averaging over
10000 runs, where each run is a game with time horizon T = 100. The associated error bars
(±1.96 × standard error) are shown in the graph.

In both cases, our strategies significantly outperform Hedge and GPS against Adversaries B
and C, while they result in comparable performance against Adversary A. Observe that against all
the three adversaries, the regret incurred by both our strategies does not significantly exceed the
upper bounds of ≈ 0.6886 for β = 0.8 and ≈ 0.9338 for β = 0.9. The regret of GPS significantly
exceeds these values in both cases by a considerable margin against Adversary C. This in particular
eliminates the possibility of GPS being exactly optimal for our problem with high probability. As
expected, the average regret incurred by the GPS algorithm does not significantly exceed the values
of ≈ 0.8333 and ≈ 1.147 respectively, which are the optimal values of regret as defined by GPS.
Similarly, considering the performance against Adversary C, Hedge appears to be sub-optimal
by a large margin for β = 0.8. But its performance comes close to the upper bound of ≈ 0.9338
for β = 0.9. This seems aligned with the possibility of Hedge being asymptotically optimal for our
problem as β → 1.

Finally, it is also interesting to note that there is no significant difference in the performance
of the 203−mode and 21−mode strategies for β = 0.8, or in the performance of the 403−mode
and 41−mode strategies for β = 0.9. This suggests the possibility of obtaining better performance
bounds for less complex strategies, potentially using some other approximation schemes.
Results for K=3. The possible losses for the experts problem with 3 experts is shown in
Figure 12.10 The resulting matrix of single stage regret vectors are shown in Figure 13.
9

Adversary B could give a loss of 1 or a loss of 0 to both experts in some stage. In this case, our algorithm stays

23

Adversary A

0.70
0.69
0.68
0.67
GPS

Adversary B

0.62
0.60
0.58
0.56
0.54
0.52
Hedge 203-mode 21-mode GPS

Adversary C
0.80
0.75
0.70

Hedge 203-mode 21-mode

GPS

Hedge 203-mode 21-mode

Figure 10: Estimates of the expected regret of different algorithms for K = 2 and β = 0.8
against the different adversaries, along with associated error bars (±1.96 × standard
error). Upper bound on optimal regret is ≈ 0.6886.

Adversary A

Adversary B

Adversary C
1.15

0.94

1.10

0.80

1.05

0.92

0.75

1.00

0.90
GPS

0.70
Hedge 403-mode 41-mode GPS

0.95
Hedge 403-mode 41-mode

GPS

Hedge 403-mode 41-mode

Figure 11: Estimates of the expected regret of different algorithms for K = 2 and β = 0.9
against the different adversaries, along with associated error bars (±1.96 × standard
error). Upper bound on optimal regret is ≈ 0.9338.
For β = 0.8 and 0.9, we approximated the frontiers using (N, n) = (20, 20), resulting in a
H(3, 20) = 1321−mode strategy in each case. The approximate value of optimal regret was ≈ 0.9067
and ≈ 1.244 respectively. The values of β n /(1 − β) in the two cases (n = 20) are ≈ 0.057 and
≈ 1.215, resulting in upper bounds of ≈ 0.9637 and ≈ 2.459 respectively. The theoretical error is
quite high in this case and hence both these upper bounds and the strategies are expected to be
crude approximations. We compared the performance of these strategies with the performance of
GPS and Hedge against the following three adversaries.
1. Adversary D: This adversary chooses one of the six possible actions uniformly at random
at each stage.
2. Adversary E: This is an optimal adversary in the GPS model for 3 experts.11 For i ≤ j,
let dij be the difference in the cumulative losses of the expert with the ith lowest loss and the
expert with the j th lowest loss. Then if d12 = d13 = 0, then with equal probability of 1/3, the
algorithm gives a loss of 0 to one expert and a loss of 1 to each of the remaining two experts.
Otherwise, with probability (1/2), the algorithm gives no loss to the leading expert and a loss
of 1 to each of the others, and with probability (1/2) it gives a loss of 1 only to the leading
expert, and no loss to others.
in the same mode at the end of the stage.
10
The optimal adversary isn’t expected to give a loss of 0 or a loss of 1 to all experts, and hence these two actions
are omitted.
11
The optimal adversary in this case is not unique; we choose one of the many mentioned in [22].

24

𝟏

𝟐

Expert 1

(𝟎, 𝟏, 𝟏)

(𝟎, −𝟏, 𝟎)

𝟎

Expert 2

(−𝟏, 𝟎, 𝟎)

(𝟏, 𝟎, 𝟏)

𝟏

Expert 3

(−𝟏, 𝟎, 𝟎) (𝟎, −𝟏, 𝟎)

𝟏

𝟐

𝟑

𝟒

𝟓

𝟔

Expert 1

𝟏

𝟎

𝟎

𝟎

𝟏

𝟏

Expert 2

𝟎

𝟏

𝟎

𝟏

𝟏

Expert 3

𝟎

𝟎

𝟏

𝟏

𝟎

Figure 12: Possible loss scenarios with 3 experts.

𝟑

𝟓

𝟔

(𝟎, 𝟎, 𝟏)

(𝟎, 𝟏, 𝟎)

𝟒

(𝟎, 𝟎, −𝟏) (𝟎, −𝟏, −𝟏)
(𝟎, 𝟎, −𝟏)

(𝟏, 𝟎, 𝟎)

(𝟏, 𝟏, 𝟎)

(𝟏, 𝟎, 𝟎)

(𝟎, 𝟎, 𝟏) (−𝟏, 𝟎 − 𝟏)
(−𝟏, −𝟏, 𝟎)

(𝟎, 𝟏, 𝟎)

Figure 13: Single-stage regret w.r.t. Experts
1, 2 and 3.

√
3. Adversary F: This adversary gives a loss of Bernoulli(1/2 − 1 − β) to expert 1 and a loss
of Bernoulli(1/2) to each of the two remaining experts at each stage.12

The results (again, over 10000 runs with horizon T = 100) are shown in Figures 14 and 15 for
β = 0.8 and 0.9 respectively.

Adversary D

Adversary E

0.86

0.85

0.88

0.84

0.87

0.82

0.86

0.80

0.85

0.78

0.83
0.82
GPS

Hedge

1321-mode

Adversary F

0.84

GPS

Hedge

0.76
1321-mode GPS

Hedge

1321-mode

Figure 14: Estimates of the expected regret of different algorithms for K = 3 and β = 0.8
against the different adversaries, along with associated error bars (±1.96 × standard
error). Upper bound on optimal regret is ≈ 0.9637.

Adversary D
1.14
1.12
1.10

Adversary E
1.16

1.13

1.14

1.12

1.12

1.11

1.10

1.10
GPS

Hedge

Adversary F

1.14

1321-mode

GPS

Hedge

1.08
1321-mode GPS

Hedge

1321-mode

Figure 15: Estimates of the expected regret of different algorithms for K = 3 and β = 0.9
against the different adversaries, along with associated error bars (±1.96 × standard
error). Upper bound on optimal regret is ≈ 2.459.
Observe that the 1321−mode strategies, despite being crude approximations, significantly outperform both GPS and Hedge against Adversary F, and their performance is comparable to these
12

If Adversary C gives a loss of 1 or a loss of 0 to all the experts in some stage, our strategy doesn’t change its
mode at the end of that stage.

25

algorithms in the remaining cases. This again suggests the possibility of obtaining tighter error
bounds for less complex strategies through other approximation techniques (although this is far
from being a comprehensive test). Unlike for the case of K = 2, we were not able to design an
adversary in this case that would rule out the optimality of GPS or Hedge with high probability.
Note that for K = 3, the optimal regret in the GPS model is ≈ 1.1111 for β = 0.8 and ≈ 1.5294
for β = 0.9.13
6.3.2

Exact characterization of V∗ for K = 2 and β = 0.5.

In some simple examples, we can exactly determine the set V∗ by “solving” the fixed point relation
given by the dynamic programming operator. We demonstrate this by determining the optimal
Pareto frontier in the game of combining expert advice (Figure 7) from 2 experts for β = 0.5.
Note that the points (0, 1/(1 − β)) = (0, 2) and (1/(1 − β), 0) = (2, 0) lie on V∗ (achieved by
choosing Expert 1 always or Expert 2 always, respectively). We can thus represent V∗ by a convex
and decreasing function f (x) defined on x ∈ [0, 2] such that f (0) = 2 and f (2) = 0, so that
V∗ = {(x, f (x)) : x ∈ [0, 2]}. βV∗ for β = 0.5 is thus the set {(βx, βf (x)) : x ∈ [0, 2]} =
{(x, 0.5f (x/0.5) : x ∈ [0, 1]}, which thus can be represented by the convex, decreasing function
f¯(x) = f (2x)/2 defined on x ∈ [0, 1], where f¯(0) = 1 and f¯(1) = 0.
( x, 1

x) + 0.5V ⇤

( 0.5, 0.5) + 0.5V ⇤

(𝟎, 𝟐)

𝑥

(𝟎, 𝟐)

𝟎. 𝟓

up(U (x))

(𝟎, 𝟏)

up(U (0.5))

(𝟎, 𝟏)

(𝟎. 𝟓, 𝟎. 𝟓)

1−𝑥

(−𝟏, 𝟎)

(𝟎, 𝟎)

𝟎. 𝟓

V⇤
𝑥

(𝟐, 𝟎)

(𝟏, 𝟎)

(x, x

(𝟎, 𝟎)

(−𝟏, 𝟎)

1) + 0.5V ⇤

V⇤
𝟎. 𝟓

(𝟏, 𝟎)

(𝟐, 𝟎)

(0.5, 0.5) + 0.5V ⇤

(𝟎, −𝟏)

(𝟎, −𝟏)

Figure 16: Construction of up(U(x)).

Figure 17: Construction of up(U(0.5)).

Now for a fixed randomization over Alice’s actions, (1 − x, x), by choosing different points in V∗
from the next stage onwards, one obtains the set of guarantees

U(x) =
max(−x + 0.5 Q1 (1), x + 0.5 Q1 (2)),


∗
max(1 − x + 0.5 Q2 (1), x − 1 + 0.5 Q2 (2)) : Q(1), Q(2) ∈ V .
(27)
If we denote the set (−x, 1 − x) + 0.5V∗ (which is obtained by mapping each element u of V∗ to
(−x, 1 − x) + 0.5u)), by U1 (x), and the set (x, x − 1) + 0.5V∗ by U2 (x), it is straightforward to see
that
up(U(x)) = up(U1 (x)) ∩ up(U2 (x)),
13

The optimal regret in the GPS model for K = 3 experts is √ 2
3

26

1−β 2

.

where up(.) is the upset of the set in [0, 2]2 . This is depicted in Figure 16. The fixed point relation
says that


∗
V = Λ ∪x∈[0,1] up(U(x)) .
From the figure, one can see that V∗ is the curve traced by the lower left corner point of up(U(x))
as x varies between 0 and 1. Since we already know that the two extreme points on V∗ are (0, 2)
and (2, 0), for x = 0.5, we know that the lower left corner point of up(U(0.5)) is (0.5, 0.5), and
hence is contained in V∗ , as shown in Figure 17. Since we know that V∗ is symmetric around the
line x = y, we know that f (x) = f −1 (x), and thus it is sufficient to determine f (x) in the range
x ∈ [0, 0.5]. In this range, f satisfies the following fixed point relation (again, see Figure 16):
f (x) = f¯(2x) + 1 − x

= f (4x)/2 + 1 − x.

(28)

Taking the derivative twice on both sides, we obtain:
f 00 (x) = 8f 00 (4x).
√
3
This gives us f 00 (x) = ax− 2 for any a ∈ R. Integrating, we obtain f (x) = a x + x + 2. Since we
√
√
want f (0.5) = 0.5, we obtain a = −2 2. Thus we have f (x) = −2 2x + x + 2. Note that f (2) = 0,
and it turns out that f (x) restricted to the domain x ∈ [0, 2] is such that f (x) = f −1 (x). Thus
√
f (x) is the function we are looking for and V∗ = {(x, −2 2x + x + 2) : x ∈ [0, 2]}.

We can compare this exact characterization with the approximate frontier that we computed
using our approximation procedure for β = 0.5 (approximation error less than 0.06). Both these
frontiers are plotted in Figure 18. As we can observe, the two frontiers are close to identical.

1.0

Exact 0.5 V ∗ (0.5)

Approx. 0.5 V ∗ (0.5)
0.8

0.6

0.4

0.2

0.0
0.0

0.2

0.4

0.6

0.8

1.0

Figure 18: Comparison of the approximation of 0.5V∗ (0.5) and the exact characterization
√
0.5V∗ (0.5) = {(x, −2 x + x + 1) : x ∈ [0, 1]}.
Optimal Policy: To attain the point (x, f (x)) for x ∈ [0, 0.5], the optimal strategy of Alice
chooses a randomization (1−x, x); then if the adversary chooses action 1, the next point she chooses
to attain is (4x, f (4x)), whereas if he chooses action 2 then the next point she chooses to attain
is (0, f (0)). To attain the point (f (x), x) for x ∈ [0, 0.5], the optimal strategy of Alice chooses
a randomization (x, 1 − x); then if the adversary chooses action 2, the next point she chooses to
attain is (f (4x), 4x), whereas if he chooses action 1, then the next point she chooses to attain is
(f (0), 0).
27

7

Conclusion and future directions.

We presented a novel set-valued dynamic programming approach to characterize and approximate
the set of minimal guarantees that a player can achieve in a discounted repeated game with vector
losses. We showed that this optimal set is the fixed point of a contractive dynamic programming
operator, and it is the Pareto frontier of some convex and closed set. We also established the
structure of the optimal strategies that achieve the different points on this set. Finally we gave
a value-iteration based procedure to approximately compute this set and also find approximately
optimal strategies. This set-valued dynamic programming approach can also be used to characterize
and approximate optimal strategies for vector repeated games with a finite time horizon. In this
case, it follows that the optimal strategy will depend on an information state belonging to a compact
set, and also the stage t.
We showed that this approach gives us a way to compute approximately regret-minimizing
strategies for playing repeated games with discounted losses, and to approximate the optimal
strategy of the uninformed player in Aumann and Maschler’s well known model of zero-sum repeated
games with incomplete information on one side
The extension of this approach to the case of long-run average losses in infinitely repeated games
is much less straightforward, despite the fact that average cost dynamic programming for standard
dynamic optimization problems like MDPs is quite well understood. Such an extension could
potentially improve our understanding of the construction of no-regret algorithms and would fill a
significant portion of the remaining gap in viewing the classical dynamic programming paradigm
as a methodical approach to designing robust decision-making algorithms.

References
[1] Jacob Abernethy, Peter L Bartlett, and Elad Hazan, Blackwell approachability and no-regret
learning are equivalent, Proceedings of The 24th Annual Conference on Learning Theory, 2011.
[2] Jacob Abernethy, Manfred K Warmuth, and Joel Yellin, Optimal strategies from random walks,
Proceedings of The 21st Annual Conference on Learning Theory, 2008.
[3] Dilip Abreu, David Pearce, and Ennio Stacchetti, Optimal cartel equilibria with imperfect
monitoring, Journal of Economic Theory 39 (1986), no. 1, 251 – 269.
[4] Dilip Abreu, David Pearce, and Ennio Stacchetti, Toward a theory of discounted repeated games
with imperfect monitoring, Econometrica 58 (1990), no. 5, pp. 1041–1063.
[5] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire, The nonstochastic
multiarmed bandit problem, SIAM Journal on Computing 32 (2002), no. 1, 48–77.
[6] Robert J. Aumann and Michael Maschler, Repeated games with incomplete information, MIT
Press, 1995.
[7] Peter L Bartlett, Wouter M Koolen, Alan Malek, Eiji Takimoto, and Manfred K Warmuth,
Minimax fixed-design linear regression, Proceedings of The 28th Annual Conference on Learning Theory, 2015.
[8] Dimitri P. Bertsekas, Dynamic programming and optimal control, vol. 1, Athena Scientific,
2005.
28

[9]

, Dynamic programming and optimal control, vol. 2, Athena Scientific, 2012.

[10] David Blackwell, An analog of the minimax theorem for vector payoffs., Pacific J. Math. 6
(1956), no. 1, 1–8.
[11]

, Controlled random walks, Proceedings of the International Congress of Mathematicians 1954 (J De Groot and J.C.H Gerretsen, eds.), vol. 3, 1956, pp. 336–338.

[12] Avrim Blum and Yishay Mansour, From external to internal regret, Journal of Machine Learning Research 8 (2007), no. Jun, 1307–1324.
[13] Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret analysis of stochastic and nonstochastic
multi-armed bandit problems, Foundations and Trends in Machine Learning 5 (2012), no. 1,
1–122.
[14] Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire,
and Manfred K. Warmuth, How to use expert advice, J. ACM 44 (1997), no. 3, 427–485.
[15] Nicolò Cesa-Bianchi and Gabor Lugosi, Prediction, learning, and games, Cambridge University
Press, 2006.
[16] Nicolò Cesa-Bianchi and Gabor Lugosi, Potential-based algorithms in on-line prediction and
game theory, Machine Learning 51 (2003), no. 3, 239–261.
[17] Alexey Chernov and Fedor Zhdanov, Prediction with expert advice under discounted loss, Algorithmic Learning Theory, Springer, 2010, pp. 255–269.
[18] Thomas M Cover, Behavior of sequential predictors of binary sequences, Tech. report, DTIC
Document, 1966.
[19] Dean P. Foster and Rakesh V. Vohra, Calibrated learning and correlated equilibrium, Games
and Economic Behavior 21 (1997), no. 1–2, 40–55.
[20] Gaëtan Fournier, Eden Kuperwasser, Orin Munk, Eilon Solan, and Avishay Weinbaum, Approachability with constraints, arXiv preprint arXiv:1712.00781 (2017).
[21] Yoav Freund and Robert E. Schapire, Adaptive game playing using multiplicative weights,
Games and Economic Behavior 29 (1999), no. 1–2, 79–103.
[22] Nick Gravin, Yuval Peres, and Balasubramanian Sivan, Towards optimal algorithms for prediction with expert advice, Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete
Algorithms, 2016.
[23] James Hannan, Approximation to Bayes risk in repeated plays, Contributions to the Theory
of Games (M. Dresher, A. W. Tucker, and P. Wolfe, eds.), vol. 3, Princeton University Press,
1957, pp. 97–139.
[24] Jeff Henrikson, Completeness and total boundedness of the Hausdorff metric, MIT Undergraduate Journal of Mathematics, Citeseer, 1999.
[25] Wouter M Koolen, The Pareto regret frontier, Advances in Neural Information Processing
Systems, 2013.

29

[26] Wouter M Koolen, Alan Malek, and Peter L Bartlett, Efficient minimax strategies for square
loss games, Advances in Neural Information Processing Systems, 2014.
[27] Wouter M Koolen, Alan Malek, Peter L Bartlett, and Yasin Abbasi, Minimax time series
prediction, Advances in Neural Information Processing Systems, 2015.
[28] Ehud Lehrer, Approachability in infinite dimensional spaces, International Journal of Game
Theory 31 (2003), no. 2, 253–268.
[29] N. Littlestone and M.K. Warmuth, The weighted majority algorithm, Information and Computation 108 (1994), no. 2, 212–261.
[30] Haipeng Luo and Robert Schapire, Towards minimax online learning with unknown time horizon, Proceedings of the 31st International Conference on Machine Learning, 2014.
[31] Jean-François Mertens, Sylvain Sorin, and Shmuel Zamir, Repeated games, vol. 55, Cambridge
University Press, 2015.
[32] James R Munkres, Topology: a first course, 1975.
[33] Vianney Perchet, Approachability, regret and calibration: Implications and equivalences, Journal of Dynamics and Games 1 (2014), no. 2, 181–254.
[34] Martin L Puterman, Markov decision processes: Discrete stochastic dynamic programming,
John Wiley & Sons, 2014.
[35] Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill, 1986.
[36] Lloyd S Shapley, Stochastic games, Proceedings of the National Academy of Sciences of the
United States of America 39 (1953), no. 10, 1095.
[37] Sylvain Sorin, A first course on zero sum repeated games, Springer, 2002.
[38] Gilles Stoltz and Gabor Lugosi, Internal regret in on-line portfolio selection, Machine Learning
59 (2005), no. 1–2, 125–159.
[39] Nicolas Vieille, Weak approachability, Mathematics of Operations Research 17 (1992), no. 4,
pp. 781–791.
[40] Volodimir G Vovk, Aggregating strategies, Proc. of Computational Learning Theory, 1990
(1990).
[41] Shmuel Zamir, Chapter 5: Repeated games of incomplete information: Zero-sum, Handbook
of Game Theory with Economic Applications (Robert Aumann and Sergiu Hart, eds.), vol. 1,
Elsevier, 1992, pp. 109–154.

A
A.1

Proof of all results
Proof of Lemma 3.1.

Consider the minimization problem:
min f (x) =
x∈S

K
X
k=1

30

xk .

Since f (x) is a continuous function defined on a compact set, it achieves this minimum value at
some point x∗ ∈ S. Hence there cannot be any point x0 ∈ S such that x0 ≺ x∗ , which means that
x∗ is on the Pareto frontier of S.

A.2

Proof of Proposition 3.1.

In order to prove the result, we need the following set of results about the Hausdorff distance:
Lemma A.1. a) h is a metric on the space of closed subsets of RK .
b) Assume that (An )n∈N is a Cauchy sequence of closed subsets of [0, 1]K . Then there is a unique
closed subset A of [0, 1]K such that h(An , A) → 0. This set A is defined as follows:
A = {x ∈ [0, 1]k : ∃xn ∈ An ∀ n s.t. xn → x}.
c) Assume that (An )n∈N is a sequence of closed subsets of [0, 1]K . Then there is a subsequence
(Ank )k∈N that converges to some closet subset A of [0, 1]K .
d) If the sets (An )n∈N in b) or c) are convex, then A is convex.
e) h(up(A), up(B)) ≤ h(A, B).
Proof. a)-c) This is the well-known completeness and compactness property of the Hausdorff metric;
see [24, 32].
d) Say that x, y ∈ A. Then x = limn xn and y = limn yn for xn ∈ An and yn ∈ An . By
convexity of each An , zn := λxn + (1 − λ)yn ∈ An . But then, zn → z := λx + (1 − λ)y. It follows
that z ∈ A, so that A is convex.
e) Let  := h(A, B). Pick x ∈ up(A). Then x = y + v for some y ∈ A and v  0. There is some
y0 ∈ B with ky − y0 k∞ ≤ . Then x0 = min{y0 + v, 1} ∈ up(B), where 1 is the vector of ones in
RK , i.e., (1; k = 1, · · · , K), and the minimization is component-wise. We claim that kx0 − xk∞ ≤ .
If y0 + v ∈ [0, 1]K , this is clear. Assume yk0 + vk > 1. Then,
x0k = 1 < yk0 + vk and xk = yk + vk ≤ 1.
Thus,
0 ≤ x0k − xk < yk0 + vk − yk − vk = yk0 − yk .

Hence, |x0k − xk | ≤ |yk0 − yk | for any k. Thus, one has kx0 − xk∞ ≤ ky0 − yk∞ ≤ .
Now we can prove the proposition. First, to show that d is a metric on F, we just need to show
that if h(up(V), up(U)) = 0 then V = U. The other properties (e.g., triangle inequality etc.) follow
from the corresponding properties for the Hausdorff metric. Note that if h(up(V), up(U)) = 0, then
up(V) = up(U). Suppose that there is some u ∈ U such that u ∈
/ V. But since u ∈ up(V), we have
u = v + y for some v ∈ V and some y  0. But since h(up(V), up(U)) = 0, by the definition of the
Hausdorff distance, for each  > 0, there is a point u in up(U) such that u  v + 1. Consider a
sequence (n )n∈N such that n → 0, and consider the corresponding sequence (un )n∈N . Now since
up(U) is compact, (un )n∈N has a convergent subsequence that converges to some u∗ ∈ up(U) such
that u∗  v  v + y = u, which contradicts the fact that u ∈ U. Thus U = V.
Next, we prove statement (b). Under the given assumptions, (up(Vn ))n∈N is Cauchy in the Hausdorff metric, so that, by Lemma A.1, there is a unique closed convex set such that h(up(Vn ), A) → 0.
31

But since h(up(Vn ), up(A)) ≤ h(up(Vn ), A) (from Lemma A.1), we have that
h(up(Vn ), up(A)) → 0 and hence up(A) = A. Thus the Pareto frontier V of A is then such that
d(Vn , V) → 0. To show uniqueness of V, assume that there is some U ∈ F such that d(Vn , U) → 0.
Then, the closed convex set up(U) is such that h(up(Vn ), up(U)) → 0. By Lemma A.1, this implies
that up(U) = up(V), so that U = V (from part (a) of the proposition) .
Finally, we prove statement (c). From statement (c) and (d) of Lemma A.1, the subsequence
(up(Vnk ))k∈N converges to some convex set A. But since h(up(Vnk ), up(A)) ≤ h(up(Vnk ), A), we
have up(A) = A. And thus the subsequence (Vnk )k∈N converges to the Pareto frontier of A, which
is in F.
Observe that it becomes clear from the above arguments that d induces these properties not just
on F, but also on the more general space of Pareto frontiers in [0, 1]K whose upset is closed.

A.3

Proof of Proposition 3.2.

Suppose that max(e(U, V), e(V, U)) ≤ . Consider a point x ∈ up(U) such that x = y + v where y ∈
U and v  0. Suppose that there is no x0 ∈ up(V) such that kx − x0 k∞ ≤ , i.e., for any x0 ∈ up(V),
kx − x0 k∞ > . This means that up(V) is a subset of the region {x0 : x0k > xk +  for some k} (this
is the region S shown in the Figure 19). But since y = x − v, we have y  x (y is in region S0 shown
in the Figure 19). But then for any w ∈ S0 , ky − wk∞ > . This contradicts the fact that for y
there is some y0 ∈ V, such that y +1  y0 . Thus d(U, V) ≤ . Now suppose that d(U, V) ≤ . Then
1

up(B)

S

B
𝝐

𝒙
𝒚

S0

S

A

1

0

Figure 19: Construction for the proof of Proposition 3.2.
for any x ∈ U, there is a x0 ∈ up(V) such that kx − x0 k∞ ≤  where x0 = y + v for y ∈ V and v  0.
Thus x + 1  x0 = y + v. The roles of U and V can be reversed. Thus max(e(U, V), e(V, U)) ≤ .
Observe that this proof uses the fact that the sup and inf in the definitions of h and e can be
replaced by max and min respectively, which is valid for the space F as discussed in footnotes 2
and 3.

A.4

Proof of Lemma 3.2:

In order to prove this lemma, we need a few intermediate results. We define the following notion
of convexity of Pareto frontiers.

32

Definition A.1. A Pareto frontier V is p-convex if for any v, u ∈ V and for each λ ∈ [0, 1], there
exists a point r ∈ V such that r  λv + (1 − λ)u.
We then show the following equivalence.
Lemma A.2. For a Pareto frontier V ⊂ [0, 1]K , the following statements are equivalent:
1. V is in F.
2. V ∈ [0, 1]K is p-convex and up(V) is closed.
Proof. To show that 1 implies 2, we just need to show that V is p-convex. To see this, suppose that
u and v are two points in V. Since they also belong to up(V), which is convex, for each λ ∈ [0, 1],
λu + (1 − λ)v ∈ up(V) and thus there is some r ∈ V such that r  λu + (1 − λ)v. Thus V is
p-convex.
To show that 2 implies 1, we just need to show that up(V) is convex if V is p-convex. To see
this, suppose that u + x and v + y are two points in up(V) where u, v ∈ V and x, y  0. By
p-convexity of V, for each λ ∈ [0, 1], there is a r ∈ V such that r  λu + (1 − λ)v and thus
r  λ(u + x) + (1 − λ)(v + y). Thus up(V) is convex.
We can now prove Lemma 3.2. Recall that,

X




αa rk (a, b) + βRk (a, b) ; k = 1, · · · , K
Ψ(V) =
max
b∈B

a∈A



: α ∈ ∆(A), R(a, b) ∈ V ∀ a ∈ A, b ∈ B .
First, note that Λ(Ψ(V)) = Λ(Ψ(up(V))). Now one can see that Ψ(up(V)) is the image of a
continuous function from the product space up(V)m×n ×∆(A) to a point in RK , which is a Hausdorff
space. Since up(V) is closed and bounded, it is compact. Also the simplex ∆(A) is compact. Thus
by Tychonoff’s theorem [35], the product space up(V)m×n × ∆(A) is compact. Hence by the closed
map lemma, f is a closed map and hence Ψ(up(V)) is closed. Hence up(Λ(Ψ(V))) is closed.
Next, recall that any point u in Λ(Ψ(V)) is of the form:

u=

max

X

b∈B

a∈A





αa rk (a, b) + βRk (a, b) ; k = 1, · · · , K

for some α ∈ ∆(A) and R(a, b) ∈ V. But since
P V is p-convex from Lemma A.2, for each b ∈ B,
there exists some Q(b) ∈ V such that Q(b)  m
a=1 αa R(a, b). Hence statement 2 follows.
Now let


u=

and

max
b∈B


v=

max
b∈B

X
a∈A

X
a∈A



αa rk (a, b) + βQk (b) ; k = 1, · · · , K


ηa rk (a, b) + βRk (b) ; k = 1, · · · , K
33

be two points in Λ(Ψ(V)), where α, η ∈ ∆(A) and Q(b), R(b) ∈ V for all b ∈ B. For a fixed
λ ∈ [0, 1], let z = αλ + η(1 − λ). Then
λu + (1 − λ)v
X
X




= λ max
αa rk (a, b) + βQk (b) + (1 − λ) max
ηa rk (a, b) + βRk (b) ; k = 1, · · · , K
b∈B




max
b∈B




max
b∈B

b∈B

a∈A

X
a∈A

X
a∈A

a∈A



za rk (a, b) + β[λQk (b) + (1 − λ)Rk (b)] ; k = 1, · · · , K


za rk (a, b) + βLk (b) ; k = 1, · · · , K .

The first inequality holds since max is a convex function and the second follows since V is p-convex,
and hence L(b) ∈ V that satisfy the given relation exist. Thus Λ(Ψ(V)) is p-convex. Combined
with the fact that up(Λ(Ψ(V))) is closed, this implies that Λ(Ψ(V)) ∈ F using Lemma A.2.

A.5

Proof of Lemma 3.3.

Suppose e(U, V) = . Let

max

X

b∈B

a∈A



αa rk (a, b) + βRk (b) ; k = 1, · · · , K

be some point in Φ(V), where α ∈ ∆(A). Then for each b, we can choose Q(b) ∈ U such that
Q(b)  R(b) + 1. We then have
max

X

b∈B

a∈A



X
αa rk (a, b) + βRk (b) + β(Qk (b) − Rk (b))
αa rk (a, b) + βQk (b)
= max
b∈B

≤ max
b∈B

= max
b∈B

a∈A

X


αa rk (a, b) + βRk (b) + β

a∈A

X


αa rk (a, b) + βRk (b) + β.

a∈A

Thus

max
b∈B

X
a∈A



But since


max
b∈B

max



αa rk (a, b) + βQk (b) ; k = 1, · · · , K

X

b∈B

X
a∈A

a∈A



αa rk (a, b) + βRk (b) ; k = 1, · · · , K + β1.



αa rk (a, b) + βQk (b) ; k = 1, · · · , K ∈ Ψ(U),

and since Φ(U) = Λ(Ψ(U)), there exists some L ∈ Φ(U) such that
34


L
Thus

max
b∈B


L

X

max
b∈B

a∈A

X
a∈A



αa rk (a, b) + βQk (b) ; k = 1, · · · , K .


αa rk (a, b) + βRk (b) ; k = 1, · · · , K


+ β1.

Thus
e(Φ(U), Φ(V)) ≤ β = βe(U, V).

A.6

(29)

Proof of Theorem 3.1.

Since Φ is a contraction in the metric d, the sequence {An } is Cauchy in F. Hence by Lemma A.1,
{An } converges to a Pareto frontier V∗ ∈ F. The continuity of the operator further implies that
V∗ = Φ(V∗ ). To show uniqueness, observe that if there are two fixed points U and V, then we have
d(U, V) = d(Φ(U, Φ(V)) ≤ βd(U, V), which implies that d(U, V) = 0 and hence U = V.

A.7

Proof of Theorem 3.2.

In G∞ , fix T ≥ 1 and consider a truncated game where Alice can guarantee the cumulative losses
in β T +1 V∗ after time T + 1. Then the minimal losses that she can guarantee after time T is the
set:


X

T +1
∗
T
αa rk (a, b) + β
Qk (b); k = 1, · · · , K | α ∈ ∆(A), Q(b) ∈ V ∀ b ∈ B
.
Λ
max β
b∈B

a∈A

This set is β T V∗ . By induction, this implies that the set of minimal losses that she can guarantee
after time 0 is V∗ .
The losses of the truncated game and of the original game differ only after time T + 1. Since
the losses at each step are bounded by (1 − β), the cumulative losses after time T + 1 are bounded
by

β T +1 (1−β)
1−β

= β T +1 . Consequently, the minimal losses of the original game must be in the set



u ∈ [0, 1]K : uk ∈ [xk − β T +1 , xk + β T +1 ] for all k, x ∈ V∗ .

Since T ≥ 1 is arbitrary, the minimal losses that Alice can guarantee in the original game must be
in V∗ .

A.8

Proof of Theorem 3.3.

Assume that Alice can guarantee every pair β T +1 u of cumulative losses with u ∈ V∗ after time
T +1 by choosing some continuation strategy in ΠA . Let x = F(p, V∗ ). We claim that after time T ,
Alice can guarantee a loss of no more than β T x on each component by first choosing aT = a with
35

probability αa (p) and then if Bob chooses b ∈ B, choosing a continuation strategy that guarantees
her F(p0 , V∗ ), where p0 = q(b, p). Indeed by following this strategy, her expected loss on component
k after time T is then
X
αa (p)rk (a, b) + β T +1 Fk (q(b, p), V∗ )} ≤ β T Fk (p, V∗ ) = β T xk .
{β T
a

Thus, this strategy for Alice guarantees that her loss after time T is no more than β T V∗ . Hence by
induction, following the indicated strategy (in the statement of the theorem) for the first T steps
and then using the continuation strategy from time T + 1 onwards, guarantees that her loss is not
more than F(p1 , V∗ ) after time 0. Now, even if Alice plays arbitrarily after time T +1 after following
the indicated strategy for the first T steps, she still guarantees that her loss is (componentwise) no
more than F(p1 , V∗ ) + β T +1 (1; k = 1, · · · , K)T . Since this is true for arbitrarily large values of T ,
playing the given strategy indefinitely guarantees that her loss is no more than F(p1 , V∗ ).

A.9

Proof of Proposition 4.1.

PM
P
Any point e in ΓN (V) is of the form M
k=1 λk = 1, and M ≤ K.
k=1 λk vk where vk ∈ up(V) and
0
But then by the definition of an upset, we have vk ∈ V for each k such that vk0  vk and hence
PM
PM
PM
0
0
k=1 λk vk ,
k=1 λk vk . By the p-convexity of V, there is some r ∈ V, such that r 
k=1 λk vk 
and hence r  e. Thus e(ΓN (V), V) = 0.

Next, we will show that for any u ∈ V, there exists e ∈ ΓN (V) such that e  u + (1/N )1.
For the rest of the proof, all the distances refer to distances in the L∞ norm. Consider a line
x = t1 +p, and suppose that the shortest distance between u and any point on this line is a > 0,
i.e., min ||u − x||∞ : x = t1 + p = a. Let x∗ = t∗ 1 + p be the point on the line that is closest
to u. If a+ , max{(x∗k − uk )+ : k = 1, · · · , K} and a− , max{−(x∗k − uk )− : k = 1, · · · , K}, then
a = max{a+ , a− }. Consider any point v that is the smallest point of intersection of x = t1 + p
and the set up(V). Then this point must lie in the set {t1 + p : t ∈ [t∗ − a+ , t∗ + a− ]}, because a)
if v = t0 1 + p for some t0 < t∗ − a+ , then it means that u dominates v which contradicts the fact
that v ∈ up(V), and b) if v = t0 1 + p for some t0 > t∗ + a− then v will strictly dominate u on each
dimension, but then the point v0 = (t∗ + a− )1 + p is strictly smaller than v and lies in up(V) and
on the line v = t0 1 + p, which contradicts the definition of v. Thus ||u − v||∞ ≤ a+ + a− ≤ 2a.
Thus we have shown that if the shortest distance between u and some line x = t1 + p is a, then
the distance between u and the smallest point of intersection of x = t1 + p and the set up(V) is no
more than 2a.
Now we will show that the for any u ∈ V, there is always a line x = t1 + p such that the
shortest distance between u and the line is no more than 1/(2N ). Let umin = mink {uk }. Then
u = umin 1 + (u − umin 1). Now the vector (u − umin 1) has value 0 on one dimension, and on
every other dimension it has value in [0, 1] (since u ∈ [0, 1]K ), and so it can be approximated by
some pk ∈ {0, 1/N, · · · , (N − 1)/N, 1} where the approximation error on any dimension is at most
1/(2N ). Thus there is a point e0 = umin 1 + p where p ∈ PN such that ku − e0 k ≤ 1/(2N ). Thus
there us always a line x = t1 + p such that the shortest distance between u and the line is no more
than 1/2N .
Together, we finally have that for any u ∈ V there is some point e00 , which is the smallest point
of intersection of some line x = t1 + p and the set up(V), such that ku − e00 k∞ ≤ 2 × (1/2N ) = 1/N ,
and thus e00  u + (1/N )1. Since there is always some point e ∈ ΓN (V) such that e  e00 (recall
36

the definition (11) of ΓN (V) as the Pareto frontier of the set ch
e  u + (1/N )1. Thus e(V, ΓN (V)) ≤ 1/N .

A.10



F(p, V) : p ∈ PN



), we have

Proof of Proposition 4.2.

We have Gn = ΓN ◦ Φ(Gn−1 )). Consider another sequence of Pareto frontiers


n
An = Φ (G0 )
.

(30)

n∈N

Then we have
d(An , Gn )

=

d(Φ(An−1 ), ΓN (Φ(Gn−1 )))

(a)

≤

d(Φ(An−1 ), Φ(Gn−1 )) + d(Φ(Gn−1 ), ΓN (Φ(Gn−1 )))

≤

βd(An−1 , Gn−1 ) +

(b)

1
,
N

(31)

where inequality (a) is the triangle inequality and (b) follows from (29) and Lemma 4.1. Coupled
with the fact that d(A0 , G0 ) = 0, we have that


1
2
n−1
d(An , Gn ) ≤
1 + β + β + ···β
N


1 1 − βn
=
.
(32)
N 1−β
Since Φ is a contraction, the sequence {An } converges to some Pareto frontier V∗ . Suppose that
we stop the generation of the sequences {An } and {Gn } at some n. Now since A0 = G0 = {0}, and
since the stage losses rk (a, b) ∈ [0, 1 − β], we have that d(A1 , A0 ) ≤ 1 − β. From the contraction

property, this implies that d(An+1 , An ) ≤ β n (1 − β). Thus d(V∗ , An ) ≤
triangle inequality we have


1 1 − βn
∗
d(V , Gn ) ≤
+ βn.
N 1−β

β n (1−β)
1−β

= β n , and thus by
(33)

Finally, to show that e(Gn , V∗ ) ≤ β n , observe that
e(Gn , An )

=

e(ΓN (Φ(Gn−1 )), Φ(An−1 ))

(a)

≤

e(ΓN (Φ(Gn−1 )), Φ(Gn−1 )) + e(Φ(Gn−1 ), Φ(An−1 ))

≤

0 + βe(Gn−1 , An−1 ).

(b)

(34)

Since A0 = G0 = {0}, this implies that e(Gn , An ) = 0 for all n. Here, (a) holds since if for three
frontiers U, V and L, U 1 -dominates V and V 2 -dominates Z, then U (1 + 2 )-dominates Z. (b)
follows from the contraction property of Φ under e. Further, e(An , V∗ ) ≤ d(An , V∗ ) ≤ β n from
above. Thus we have e(Gn , V∗ ) ≤ e(Gn , An ) + e(An , V∗ ) ≤ β n .

37

A.11

Proof of Proposition 4.3.

In order to prove this result, we need a few intermediate definitions and results. First, we need to
characterize the losses guaranteed by any H(K, N )−mode stationary strategy. Such a strategy π
defines the following operator on any function F : PN → RK (PN is defined in (9)):
∆πN (F)(p)


=

max
b∈B

X

αa (p)rk (a, b) +

K
X
k0 =1

a∈A


zk0 (b, p)βFk (qk0 (b, p)) ; k = 1, · · · , K ,

(35)

where qk0 (b, p) ∈ PN for all k 0 . Now for a function F : PN → RK , define the following norm:
kFk = max kF(p)k∞ .
p∈PN

It is easy to show that ∆πN is a contraction in the norm. We omit the proof for the sake of brevity.
Lemma A.3.
k∆πN (F) − ∆πN (G)k ≤ βkF − Gk.

(36)

We can then show the following result.
Lemma A.4. Consider a H(K, N )-mode strategy π. Then there is a unique function
Fπ : PN → RK
such that ∆πN (Fπ ) = Fπ . Further, The strategy π initiated at mode p where p ∈ PN guarantees the
vector of losses Fπ (p).
The first part of the result follows from the fact that the operator is a contraction and the
completeness of the space of vector-valued functions with a finite domain for the given norm. The
second part follows from arguments similar to those in the proof of Theorem 3.3. The arguments
are not repeated here for the sake of brevity. Now let


πn
πn
V , Λ ch({F (p) : p ∈ PN ) ,
where Fπn is the fixed point of the operator ∆πNn .
Define a sequence of functions Fn : PN → RK where Fn (p) = F(p, Φ(Gn−1 )) = F(p, Gn ). We
then have that
d(Vπn , V∗ ) ≤ d(Vπn , Gn ) + d(Gn , V∗ )


1 1 − βn
πn
≤ d(V , Gn ) +
+ βn.
N 1−β

(37)
(38)

From the definition of d, it is clear that d(Vπn , Gn ) ≤ kFπn − Fn k. Next we have
kFπn − Fn k

≤

kFπn − ∆πNn (Fn )k + k∆πNn (Fn ) − Fn k

(39)

=

k∆πNn (Fπn ) − ∆πNn (Fn )k + kFn+1 − Fn k

(40)

βkFπn − Fn k + kFn+1 − Fn k.

(41)

(a)
(b)

≤

38

(42)

Here (a) holds because ∆πNn (Fn ) = Fn+1 by the definition of the strategy πn , and because Fπn is a
fixed point of the operator ∆πNn . (b) holds because ∆πNn is a contraction. Thus we have
d(Vπn , Gn ) ≤ kFπn − Fn k ≤

kFn+1 − Fn k
.
1−β

(43)

And finally we have:
1
d(V , V ) ≤
N
πn

∗



1 − βn
1−β



+ βn +

kFn+1 − Fn k
.
1−β

(44)

To finish up, we need the following result:
Lemma A.5.
kFn+1 − Fn k ≤ d(Gn+1 , Gn ).
Proof. Let u = Fn+1 (p) and v = Fn (p) for some p. Now u is the point of intersection of Gn+1
and the line x = t1 + p. v is the point of intersection of the frontier Gn and the line x = t1 + p,.
Now suppose that ku − vk∞ > d(Gn+1 , Gn ). Then either for u, there is no r ∈ Gn such that
r  u + 1d(Gn+1 , Gn ) or for v, there is no r ∈ Gn+1 such that r  v + 1d(Gn+1 , Gn ). Either of the
two cases contradict the definition of d(Gn+1 , Gn ). Thus ku − vk∞ ≤ d(Gn+1 , Gn ).
Finally, by the triangle inequality we have

d(Gn+1 , Gn ) ≤ d(An+1 , An ) + d(Gn+1 , An+1 ) + d(Gn , An )




1 1 − βn
1 1 − β n+1
n
+
.
≤ (1 − β)β +
N
1−β
N 1−β

(45)
(46)

Combining with (44) we have the result.

B

Some remarks on Pareto frontiers of closed and convex sets.

The Pareto frontier of a closed set is not necessarily closed. Figure 1 is one example – the upset is
closed, but its Pareto frontier is open. But we can show that the Pareto frontier of a closed and
convex set in R2 is closed.14
Proposition B.1. Let V be the lower Pareto frontier of a closed and convex set S in R2 . Then V
is closed.
Proof. Suppose that {vn } is a sequence of points in V that converge to some point v. Then since
S is closed, v ∈ S. We will show that v ∈ V. Suppose not. Then there is some u ∈ V such that
u  v. Suppose first that u1 < v1 and u2 < v2 . Then let  = (min(v1 − u1 , v2 − u2 )/2 and consider
the L2 ball of radius  around v, i.e.
Bv () = {y ∈ R2 : ky − vk2 ≤ }.
14
Of course, the Pareto frontier of a closed set may be empty, e.g., {(x, y) ∈ R2 : x = y}, in which case it is trivially
closed.

39

Then for any point y in Bv (), we have that u  y. But since {vn } converges to v, there exists some
point in the sequence that is in Bv (), and u is dominated by this point, which is a contradiction.
Hence either u1 = v1 or u2 = v2 . Suppose w.l.o.g. that u1 < v1 and u2 = v2 . See Figure 20. Let
δ = (v1 − u1 )/2 and consider the ball of radius δ centered at v, i.e. Bv (δ). Let vn be a point in the
sequence such that vn ∈ Bv (δ). Now vn,1 > u1 and hence it must be that vn,2 < u2 . Now for some
λ ∈ (0, 1), consider a point r = λu + (1 − λ)vn such that r1 = u1 + δ. It is possible to pick such a
point since a) v1 = u1 + 2δ and b) |vn,1 − v1 | ≤ δ, which together imply that vn,1 ≥ u1 + δ (please
see the figure). Now r ∈ S since S is convex. Next r1 = v1 − δ < v1 , and also r2 < u2 = v2 since

𝜹

𝜹

𝒖

𝒗
𝜹%
𝒓
𝒗𝒏

Figure 20: Construction in the proof of Proposition B.1.
λ > 0 and vn,2 < u2 . Let δ 0 = v2 − r2 . Then consider the ball Bv (δ 0 ) centered at v. Clearly r  y
for any y ∈ Bv (δ 0 ). But since {vn } converges to v, there exists some point in the sequence that is
in Bv (δ 0 ), and r is dominated by this point, which is again a contradiction. Thus v ∈ V.
Interestingly, this result doesn’t hold for closed and convex sets in RK for K > 2, as we show
in the example depicted in Figure 21. The closed and convex set S is a solid 3-dimensional cone
with apex (0, 0, 1) and base being the semicircular disc defined by the set {(x, y, z) ∈ R3 : x =
5, (y − 1)2 + (z − 1)2 ≤ 1, z ≤ 1}. The sequence (vn )n∈N lies on the Pareto frontier of this set as
shown in the figure, but it converges to the point (5, 0, 1), which dominates the point (0, 0, 1).

40

𝒛

(𝟎, 𝟎, 𝟏)

S

𝒚

𝒗∗ = (𝟓, 𝟎, 𝟏)

𝒗𝒏
𝒙

Figure 21: An example of a compact and convex set in R3 whose Pareto frontier is not closed. The
sequence (vn ) on the Pareto frontier converges to the point (5, 0, 1), which dominates (0, 0, 1).

C

Solving Linear Program (12).

When V is the lower Pareto frontier of a convex polytope, (12) is a linear program. In this program,
x is a dependent vector and can be eliminated. The only question remains is that of addressing
the constraint Q(b) ∈ V. The vertices of V are a subset of {F(p, Φ(V)) : p ∈ PN }. Thus Q(b)
can be chosen as a convex combination of points in {F(p, Φ(V)) : p ∈ PN }. This introduces
H(K, N ) variables for each b ∈ B along with the constraint that these variables sum to 1, thus
contributing mH(K, N ) variables and m constraints. Along with the variables α and t, this makes
mH(K, N ) + l + 1 variables inPtotal. And along with the K domination constraints for each
b ∈ B and the constraint that a αa = 1, this makes Km + m + 1 constraints in total (ignoring
non-negativity constraints on all variables except t).
Of the H(K, N ) variables associated with each b ∈ B that determine the point Q(b), we know
that at most K will be non-zero. This sparsity constraint can potentially be utilized to speed up
the computation, although we didn’t attempt to do so in our computations.

D

GPS algorithms.

The GPS algorithms are defined as follows [22]. Let ξ = (1 −

p
1 − β 2 )/β.

1. K=2: Let d be the difference in the cumulative (undiscounted) losses of the leading expert
(the one with the lower cumulative loss) and the lagging expert (the one with the higher loss).
Then at every stage, the algorithm chooses the leading expert with probability 1 − (1/2)ξ d
and the lagging expert with probability (1/2)ξ d .
41

2. K=3: For i ≤ j, let dij be the difference in the cumulative losses of the expert with the
ith lowest loss and the expert with the j th lowest loss. Then the algorithm chooses the
leading expert with probability 1 − ξ d12 /2 − ξ d13 +d23 /6, the second expert with probability
ξ d12 /2 − ξ d13 +d23 /6 and the lagging expert with probability ξ d13 +d23 /3.

E

A Blackwell-type minmax theorem doesn’t hold for finite games.

Here we give an example showing that a Blackwell-type minmax result doesn’t hold for expected
losses in finite games, even if the losses are scalar. Consider the matrix game shown in Figure 22.
And consider the convex set consisting of a single point 0.4 on the real line. Then observe that for
any mixed strategy (α, 1 − α) of player 1, the expected loss if player 2 chooses action 1 is (1 − α)
and if she chooses action 2, it is 0.25α + 0.5(1 − α) = 0.5 − .25α. Thus no strategy of player 1 can
guarantee that the expected loss is exactly 0.4 irrespective of the actions of player 2. But neither
does player 2 have any strategy that guarantees that the expected loss in the game is not 0.4. To
see this, observe that for any strategy (γ, 1 − γ) of player 2, player 1 can choose a randomization
over her two actions that will result in an expected loss of exactly 0.4.
𝟏

𝟐

𝟏

𝟎

𝟎. 𝟐𝟓

𝟐

𝟏

𝟎. 𝟓

Figure 22: A game with scalar losses.

42

