Abstract
The problem of controlling a finite state Markov chain in the presence of an adversary so as to ensure desired performance levels for a vector of objectives is cast in the framework of Blackwell approachability. Relying on an elementary two time scale construction a control scheme is proposed which ensures almost sure convergence to the desired set regardless of the adversarial actions.
Introduction
Many control problems in practice have two features that put them outside of the classical framework of deterministic or stochastic optimal control theory: presence of unknown disturbances and multiple objectives. One common approach for addressing the former issue is to treat the disturbances as actions of an adversary and plan against the worst case scenario thereof. This makes the problem a two person zero sum game. While the classical two person zero sum stochastic games are fully analyzable through the associated Shapley equation, this is not the case when there are many objectives. In a seminal article, Blackwell [1] provided a framework for addressing this 'vector minmax' problem in case of repeated games, providing both the necessary and sufficient conditions for attainability of the objectives (what came to be known as Blackwell approachability) and a scheme for achieving the same. This is becoming a popular model for addressing engineering problems with aforementioned features, see, e.g., Hou et al [2] for a recent application. The framework has also found application in strategic learning literature in economics and computer science, see, e.g., Young [5] . As observed above, many engineering situations call for going beyond the repeated game model and consider a controlled Markov dynamics instead. In an important work, Shimkin and Shwartz [4] studied this problem for controlled Markov chains and proposed a scheme to ensure Blackwell approachability. Their scheme depends on updating strategies at return times to a fixed state, which allows them to exploit the regenerative nature of such visits. This is necessitated by the fact that there appears to be a need to hold the policy fixed for some time -the interval between two return times in their case -for the 'learning' to take place. For a large chain, the return times can be infrequent, rendering the convergence slower. Motivated by this, we propose an alternative scheme here that holds a policy constant for durations that are short initially and can become longer gradually, thus capturing the 'exploration-exploitation' trade-off. Each choice of strategy is associated with a positive re-scaled time duration and whenever the player switches to a new strategy he retains it for the associated re-scaled duration of time. Almost sure convergence of the running average cost to the desired set is then established under standard conditions. A major ingredient in our proof is an elementary two time scale argument and the proposed scheme is designed to exploit the two time scale feature in an essential way.
The paper is organized as follows. Section 2 describes the problem setup and introduces the notation and some preliminary concepts. Section 3 develops an elementary two time scale result which plays a crucial role in the proof of convergence and around which our scheme is built in the first place. Section 4 proves the main convergence result, Theorem 18. Section 5 concludes by outlining some further possibilities.
Basic setup
The model. Consider a system evolving as a controlled Markov chain on a finite state space S with a reward associated with each transition. We assume that the reward is always some vector from a compact set K ⊂ R d .
Let U p and U a be finite action spaces. Let (θ n ) denote the aforementioned controlled Markov chain on S with transition kernel p(θ
denote the set of probability distributions on the space U p . Let Π p denote the set of all maps, or strategies, from S to P(U p ). Similarly, let Π a denote the set of all strategies from S to P(U a ). Depending on the past the player and the adversary independently choose their current strategies from Π p and Π a respectively. Let (u p n ), (u a n ) be the actual control sequences chosen by the player and the adversary from U p , U a respectively. At time step n the one step reward is given by κ (θ n , u p n , u a n ). Let x n denote the vector for current average reward. The iterative equation for the average reward becomes
Main goal. The aim of the main player is to have the average reward asymptotically approach a certain desirable subset D ⊂ K ⊂ R d by suitably choosing his strategy at each step. More precisely, the player seeks to choose his sequence of strategies in such a manner that no matter what sequence of strategies the adversary chooses, with probability one all limit points of the sequence (x n ) lie inD whereD denotes the closure of D.
Assumptions. In our analysis we restrict our attention to the case wherē D is convex. However, see Section 5 for possible extension to the case of non-convexD. Next, assume that when the strategies for the main player and the adversary are held fixed at arbitrary strategies π p ∈ Π p and π a ∈ Π a respectively then the Markov chain (θ n ) is ergodic. Let η (π p ,π a ) (·) denote the corresponding stationary measure on state space S with the strategies for the player and the adversary held fixed. Define the corresponding average rewardκ(π p , π a ) as
For any point x, let xD be the (unique) point inD closest to x. For the rest of this paper we work under the following assumption which is standard for Blackwell approachability: Assumption 1. For every x ∈ K\D there exists a player strategy π p x satisfying the following inequality:
In words, the hyperplane through xD perpendicular to the line segment xxD separates x from the set {κ(π
For ρ ∈ R + , let B(x, ρ) denote the open ball of radius ρ centered at x.
Lemma 1.
There exists a map ρ(·) : K\D −→ R + , such that for any x ∈ K\D, we have
Proof. For any x ∈ K\D, by Assumption 1 there exists a player strategy π
and an ǫ > 0 such that
We get
x , π a ) − xD < ∞ and sup y∈K yD − y < ∞, it follows that there exists a finite positive constant c such that
SinceD is convex, the map x → xD must be continuous. It follows that there exists a ρ(x) > 0 such that κ(π p x , π a ) − yD, yD − y > ǫ/2 whenever x − y < ρ(x). Since this holds for any π a , we get
For the rest of the paper we assume that ρ(·) : K\D → R + is a function satisfying (1) . We now introduce the main objects needed for our analysis.
The sets K n , Q n and Q. For n ∈ N, define compact sets K n as
We can write
By compactness there exists a finite subcover. Let Q n be a finite subset of
Let Q denote the union
The following result is immediate.
Proposition 2. The collection Q is a countable collection.
The map Q(·). Since Q is countable, we can assign an injective (one-one) map I : Q −→ N. Using the map I(·) we define a map Q : K\D → Q where, for x ∈ K\D, we define
The re-scaled times and the interpolated trajectory. Let t(0) = 0. For n ∈ N, define the re-scaled times
Letx(·) be the trajectory obtained by linearly interpolating between the iterates. Thus, for any n ∈ N and t ∈ [t(n), t(n + 1)) definē
p , u a ) ∈ K and K is compact, it follows that v max < ∞. Clearly, for times u 1 and u 2 ,
Let T : Q → R + be a map such that for every q ∈ Q the following holds:
Choice of strategy along S. We are now ready to define how the player should choose his strategies over time. Let π p 0 be any arbitrary strategy. Let S := (s n ) denote the increasing subsequence of times when the player changes his strategy. Start with s 0 = 0. Assume s n is known. We consider two cases, x sn ∈ K\D and x sn ∈D. If x sn ∈ K\D then set q = Q(x sn ). Now choose the strategy π p q and set
If, however, x sn ∈D then choose the strategy π p 0 and set s (n+1) = s n + 1.
A two time scale result
This section develops an elementary two time scale result needed for the proof of convergence. For the reader's convenience we break the proof into a series of smaller units.
Proof. If y ∈ B(x, ρ(x)) ∩D, then yD = y and so
But this contradicts (1). Hence, B(x, ρ(x)) ∩D = ∅.
Proof. Since both L andD are compact sets, it follows that inf x∈D,y∈L
Consider any q such that q ∈ Q m and m >
Further, by Lemma 3,
and q ∈ Q m then B(q, ρ(q)/2) L = ∅. The result follows.
Lemma 5. Let (s m(n) ) be an increasing subsequence of S. If lim n→∞ x s m(n) = x for some x ∈ K\D, then along a further subsequence, denoted (s m(n) ) again, there exists q ∈ Q such that Q(x s m(n) ) = q for all n ∈ N.
Proof. Since lim n→∞ x s m(n) = x / ∈D, there exists a compact set L such that L ∩D = ∅ and x s m(n) ∈ L for all sufficiently large n. By Lemma 4,
Thus there exists q ∈ Q such that along a subsequence, denoted (s m(n) ) again, we have x s m(n) ∈ L and Q(x s m(n) ) = q for all n ∈ N.
The Mannor-Tsitsiklis bound.
We now introduce a set of conditions, labeled ( †), which is needed for Theorem 6 and Corollary 7 below. To this end, let (s m(n) ) be an arbitrary increasing subsequence of S. Let T l and T r be times such that T l < T r . Let (l m(n) ) and (r m(n) ) be sequences such that s m(n) ≤ l m(n) < r m(n) ≤ s m(n)+1 , n ∈ N. Let ( †) denote the following four conditions:
2 † Q(x s m(n) ) = q for some q ∈ Q and all n ∈ N.
Assuming the conditions of ( †) hold, for l m(n) (n) , . . . , r m(n) − 1, . The rewards κ τ (θ, u a ), τ = 1, 2, . . . , are independent, identically distributed random variables with mean
Further, since each κ θ j , u p j , u a j is chosen from a compact set, we get, for z in any neighbourhood of the origin,
where ·, · is the inner product in R d . Define the set R(π
We can now invoke Theorem 6.2 of Mannor and Tsitsiklis [3] . For our setup and with our notation, it reads as follows:
Theorem 6. Assuming that the conditions of ( †) hold, there exists a function λ : (0, ∞) → (0, ∞] and a positive constant c 0 , such that irrespective of the adversary policy π a , the following bound holds:
For the next result, note that t(r
1/j. Under the conditions of ( †) this implies that
Corollary 7. Assuming that the conditions of ( †) hold, we have
for n sufficiently large. Plugging this estimate in Theorem 6 and noting that the constant ǫ is arbitrary, a standard application of the Borel-Cantelli argument gives the result.
The two time scale result. With Corollary 7 available for use, we are ready for our main two time scale result. Thus, let (s m(n) ) be an arbitrary increasing subsequence of S. Assume that lim n→∞ x s m(n) = x for some x ∈ K\D. By Lemma 5 there exists a q ∈ Q such that along a subsequence, denoted again by (s m(n) ), Q(x s m(n) ) = q for all n ∈ N. For n ∈ N and t ≥ 0 define the trajectories
By the Arzela-Ascoli theorem there exists a continuous trajectoryȳ(·) such that along a subsequence, denoted again by (m(n)), lim n→∞ȳm(n) (·) =ȳ(·) in the topology of uniform convergence over compacts. Set T = T (q). For k ∈ N and J k = {0, 1, . . . , 2 k − 1} consider the finite collection of intervals
For j ∈ J k , define
Next, with (s m(n) ) denoting an arbitrary increasing subsequence of S, define N(q, j, k) as the following set:
.
In terms of l m(n) and r m(n) , the equation for average reward can be written as
Rearranging, we get
and consequently
Hence, by Corollary 7 it must be the case that
Define C := k C k . The next fact is crucial to our analysis.
Proposition 9. The collection C is a countable collection of intervals.
Define N to be the following set:
Proposition 10. The event N is a null set, i.e., P[N] = 0.
Proof. Both Q and C are countable collections. The result now follows from the fact that the union of countably many exceptional null sets is again a null set.
By virtue of Proposition 3, to show almost sure convergence of sequences (x n ) toD it suffices to restrict attention to sequences outside N. Consequently, in what follows we shall work exclusively with sequences (x n ) outside the exceptional null set N.
Theorem 11. Let (x n ) be any sequence outside the exceptional null set N. For (s m(n) ) an increasing subsequence of S, assume that lim n→∞ x s m(n) = x for some x ∈ K\D. Assume further that for some q ∈ Q, Q(x s m(n) ) = q for all n ∈ N. Let T = T (q). Letȳ(·) be a limiting trajectory of the trajectories y m(n) (·) given by (4) . Then, for t ∈ [0, T ],ȳ(t) can be written as
where
Lebesgue almost all t in [0, T ], the following holds:
Remark. We point out that (6) is a standard result in two time scale theory. Moreover, using Lebesque's theorem we could also show (7) to hold almost surely for any (but not all) t ∈ [0, T ]. The problem arises from the fact that the set [0, T ] is an uncountable set and when we do a union of null sets, one for each t ∈ [0, T ], the union need not be a null set. We solve this problem by treating the interval [0, T ) as a probability space and giving the trajectoryȳ(t) a martingale structure. This also provides an independent and elementary proof of two time scale structure.
Proof. Define G k := σ (C k ), the σ-algebra on [0, T ) generated by C k . Let G := k G k . For λ the Lebesgue measure, define the scaled probability measure µ on [0, T ) given by dµ/dλ = 1/T . This acts as a probability measure for the probability space
In other words, the sequence (M k (·)) k∈N forms a bounded martingale in the filtered probability space ([0, T ), µ, G, G k ). It follows that µ-almost surely the limit v(t) := lim k→∞ M k (t) exists. The limit v(·) is, clearly, a measurable function. Note that [0,
Letting k → ∞ gives us:ȳ
Note that as t ranges over [0, T ), the pair (j(k), k) still take values in a countable set. From the definitions of M k (t) and κ j,k it follows that
Since (x n ) is outside the exceptional null set N, lim k→∞ κ j(k),k must necessarily lie in R(π p q ).
Lemma 12. Let (x n ) be any sequence outside the exceptional null set N. For (s m(n) ) an increasing subsequence of S, assume that lim n→∞ x s m(n) = x for some x ∈ K\D. Assume further that for some q ∈ Q, Q(x s m(n) ) = q for all n ∈ N. Let T = T (q). Letȳ(·) be a limiting trajectory of the trajectories y m(n) (·) given by (4) . Then
Proof. For t ∈ [0, T ) let d(t) := inf w∈D ȳ(t) − w . For any point p, let d p (t) := ȳ(t) − p . LetȳD(t) be the point inD closest toȳ(t). We havė
and the result follows.
Almost sure convergence
As before we present our proof as a series of short lemmas.
Lemma 13. For s n ∈ S, if x sn ∈D then
Lemma 14. For x ∈ K\D we have
Proof. By definition, x ∈ B(Q(x), ρ(Q(x))/2). It follows from Lemma 3 that
The result now follows from (2).
Since s m(n) → ∞ as n → ∞, the result follows .
Lemma 16. Let (s m(n) ) be an increasing subsequence of S such that lim n→∞ x s m(n) = x and lim n→∞ x s m(n)+1 = y. If y ∈ K\D then x ∈ K\D.
This leads to a contradiction since y ∈ K\D.
Recall that S = (s n ) is the increasing sequence of times when the player changes his strategy.
Lemma 17. Let (x n ) be a sequence outside the exceptional null set N. If y is a limit point of the sequence (x sn ) then y ∈D.
Proof. Assume to the contrary and let y be a limit point of (x sn ) that is farthest fromD. Take an appropriate subsequence such that lim n→∞ x s m(n) = x and lim n→∞ x s m(n)+1 = y. By Lemma 16 x ∈ K\D. Further assume, by Lemma 5 , that the subsequence is such that Q(x s m(n) ) = q for some q ∈ Q and all n ∈ N. Since T (q) > 0 this leads to a contradiction and the result follows.
Theorem 18. Let (x n ) be a sequence outside the exceptional null set N. If x is a limit point of the sequence (x n ) then x ∈D.
Proof. By taking suitable subsequences assume that lim n→∞ x u m(n) = x where s m(n) < u m(n) ≤ s m(n)+1 for all n ∈ N with (s m(n) ) some increasing subsequence of S. Assume further that lim n→∞ x s m(n) = y for some y. By Lemma 17 y ∈D. Since x u m(n) − x s m(n) ≤ v max (t(s m(n)+1 ) − t(s m(n) )), it follows from Lemma 15 that lim n→∞ x u m(n) − x s m(n) = 0. Thus x = y and the result follows.
Conclusion
We have established the a.s. convergence of our scheme to the desired limit set for finite state controlled Markov chains. In conclusion we point out some future directions.
Extension to non-convex D. For non-convex D in general, the existence of a 'nearest point' inD from any point outsideD is guaranteed. A scheme along above lines can be conceived wherein one uses piecewise constant policies that ensure decrease of distance fromD if such policies are known to exist.
Countable state space. Under suitable uniform stability assumption or 'near-monotonicity' condition on costs, variations of the above scheme can be proposed for Blackwell approachability. This will be pursued in a future work.
Computational issues. The above scheme is an 'ideal' scheme in so far as it ignores actual computational aspects. A practical implementation would raise further issues such as recursive on-line computation of policies, learning, etc.
A combination scheme. A variation that seems promising is to combine the approaches of this paper and Shimkin and Shwartz [4] , switching strategies when the currently adopted strategy exhausts its allotted time, or when the chain returns to a prescribed state, whichever occurs first. One expects similar results, though the analysis will be messier.

{'paper_id': '117057189', 'title': 'A vector minmax problem for controlled Markov chains', 's2_url': 'https://api.semanticscholar.org/CorpusID:117057189', 'source': 'S2ORC'}