Eugenio Della Vecchia

Silvia Di

Alain Jean-Marie
email: alain.jean-marie@inria.fr.

Rolling horizon procedures in Semi-Markov Games: The Discounted Case

Keywords:

 for Markov Games, both in discrete time. In this way we generalize the results on the rolling horizon and approximate rolling horizon procedures previously obtained for discrete-time problems.

Procédures d'horizon roulant dans les jeux semi-Markoviens: le cas actualisé Résumé : Nous étudions les propriétés de la procédure de décision à horizon roulant et une approximation de cette procédure, pour le cas de jeux semi-Markoviens à somme nulle avec horizon infini et actualisation, quand l'espace d'états est un ensemble borélien et les espaces d'actions sont compacts. Sous des hypothèses appropriées, nous montrons que l'équilibre est l'unique solution de l'équation de programmation dynamique associée au jeu, puis nous prouvons des bornes d'erreur impliquant la convergence des procédures quand l'horizon de programmation tend vers l'infini. Notre approche est basée sur le formalisme pour les jeux semi-Markoviens développé par Luque-Vásquez [START_REF] Luque-Vásquez | Zero-sum semi-Markov game in Borel spaces with discounted payoff[END_REF], joint à des extensions des résultats de Hernández-Lerma et Lasserre [START_REF] Hernández-Lerma | Error Bounds for Rolling Horizon Policies in Discrete-Time Markov Control Processes[END_REF] pour les processus de décision Markoviens et Chang et Marcus [START_REF] Chang | Two-person zero-sum games: receding horizon approach[END_REF] pour les jeux Markoviens, ces deux derniers travaux étant en temps discret. De cette façon, nous généralisons les résultats sur la procédure à horizon roulant obtenus pour les problèmes en temps discret.

Mots-clés : Jeux semi-Markoviens, procédure à horizon roulant [START_REF] Bhattacharya | Controlled semi-Markov models -the discounted case[END_REF] Introduction

In this work we analyze two approximation procedures applied to zero-sum semi-Markov games with the expected total discounted reward as the performance criterion. Specifically, we work with methods derived from the Rolling Horizon procedure. Semi-Markov Games (SMG) generalize Markov Games (MG) by allowing the decision maker to choose actions whenever the system state changes, modeling the system evolution in continuous-time and allowing the time spent in a particular state to follow an arbitrary probability distribution. The system state may change several times between decision epochs but only the state at a decision epoch is relevant to the decision maker. SMG with discounted reward are analyzed in [START_REF] Luque-Vásquez | Zero-sum semi-Markov game in Borel spaces with discounted payoff[END_REF] and later, in [START_REF] Jaśkiewicz | Stochastic Games with Unbounded Payoffs: Applications to Robust Control in Economics[END_REF][START_REF] Minjárez-Sosa | Two Person Zero-Sum Semi-Markov Games with Unknown Holding Times Distribution on One Side: A Discounted Payoff Criterion[END_REF]. All these papers deal with the characterization of the value function as the fixed point of certain dynamical programming operators.

On the other hand, Rolling Horizon (RH) control is an usual procedure for making decisions in many infinite stage decision problems. It is based on choosing the best most immediate action based on the knowledge of the information of the problem just for a certain number of periods in the future. One design issue of the controller will be then to determine how many periods in the future must be taken into account, in order to make the optimal immediate decision [START_REF] Sethi | A Theory of Rolling Horizon Decision Making[END_REF]. RH strategies are largely used in several areas: we can mention here production control problems, stabilization of control systems, and macro-planning problems. The study of this and other applications can be found in [START_REF] Kwon | Receding Horizon Control. Predictive Control for State Models[END_REF].

The objective of the present work is to extend the analysis of the accuracy of the RH method and of an Approximate Rolling Horizon (ARH) method to SMG with the total discounted reward criterion, when the state space is assumed to be Borel, and the action spaces compact. As mentioned previously, the SMG structure was studied from the theoretical viewpoint by [START_REF] Luque-Vásquez | Zero-sum semi-Markov game in Borel spaces with discounted payoff[END_REF] and we borrow some of their results. On the one hand, [START_REF] Hernández-Lerma | Error Bounds for Rolling Horizon Policies in Discrete-Time Markov Control Processes[END_REF][START_REF] Hernández-Lerma | Value iteration and rolling plans for Markov control processes with unbounded rewards[END_REF][START_REF] Chang | Two-person zero-sum games: receding horizon approach[END_REF] can be seen as particular cases of our results shown here because the two first investigate the accuracy of the RH procedure for discrete-time Markov Decision Processes (MDP) (just one decision-maker) with bounded and unbounded rewards functions, respectively, and the last one deals with discrete-time zero-sum Markov games with finite state spaces. The present work also extends our previous work [START_REF] Vecchia | Rolling Horizon Procedure on Controlled Semi-Markov Models. The Discounted Case[END_REF] where we study the RH procedure applied to semi-Markov Decision Processes (SMDP) (continuous temporal evolution of the problem where just one decision maker acts). Also as a particular case, all the results obtained here apply to continuous-time MG where, up to our knowledge, RH and ARH have not been applied so far. This paper is organized as follows. In Section 2, we present the SMG model, introduce its notation and state the assumptions on the data of the problem. In Section 3 we present the performance criterion and the dynamic programming operator for this case, mentioning the results on the associated optimality equation and recursion scheme. We prove characterization and optimality results under assumptions that are, up to our knowledge, more general than those used in the literature.

Section 4 contains our contributions about the convergence of the values of RH and ARH policies to the values of the game. The approach in this section is based on [START_REF] Hernández-Lerma | Value iteration and rolling plans for Markov control processes with unbounded rewards[END_REF] where the case of discrete-time MDP is treated, and on [START_REF] Chang | Two-person zero-sum games: receding horizon approach[END_REF] for the case of finite state spaces. As compared with this last work, we have not only proved results of the ARH for more general state spaces and possibly unbounded cost functions, but we also have improved significantly the error bounds. Finally, Section 5 is devoted to the concluding remarks.

Preliminaries and Notations

We consider a semi-Markov game of the form ▼ ✿❂ ✭❙❀ ❆❀ ❇❀ ❢❆ s ✿ s ✷ ❙❣❀ ❢❇ s ✿ s ✷ ❙❣❀ ◗❀ ❋❀ ❵❀ ☛✮ where • ❙ is the state space.

• ❆ and ❇ are the action spaces for players 1 and 2 respectively. • For every s ✷ ❙, we define the sets ❆ s and ❇ s as the sets of actions available in state s for respective players, and, therefore

❆ ❂ ❬ s✷❙ ❆ s ❀ ❇ ❂ ❬ s✷❙ ❇ s ✿ • We set ❑ ❂ ❢✭s❀ ❛❀ ❜✮ ✿ s ✷ ❙❀ ❛ ✷ ❆ s ❀ ❜ ✷ ❇ s ❣.
• The transition law ◗✭✁•✁✮, is a stochastic kernel on ❙ given ❑, and ❋ ✭✁•s❀ ❛❀ ❜✮ is the distribution function of the holding time in state s ✷ ❙ when actions ❛ ✷ ❆ s and ❜ ✷ ❇ s are chosen.

• The reward function is ❵ ✿ ❑ ✼ ✦ | and ☛ is a discount factor.

If at time of the ♥-th decision epoch, the state of the system is s ♥ ❂ s, and the chosen actions are ❛ ♥ ✷ ❆ s and ❜ ♥ ✷ ❇ s , then the system remains in the state s during a nonnegative random time ✍ ♥✰✶ with distribution ❋ ✭✁•s ♥ ❀ ❛ ♥ ❀ ❜ ♥ ✮ and a continuously discounted, stationary reward ❵✭s ♥ ❀ ❛ ♥ ❀ ❜ ♥ ✮ is received by player 1 and paid by player 2. The decision epochs are therefore ❚ ♥ ✿❂ ❚ ♥ ✶ ✰ ✍ ♥ for ♥ ❂ ✶, and ❚ ✵ ❂ ✵. The random variable ✍ ♥✰✶ ❂ ❚ ♥✰✶ ❚ ♥ is called the sojourn or holding time at stage ♥.

For Borel sets ❳ and ( , we will note with P✭❳✮ the family of probability measures on ❳ endowed with the weak topology, and with P✭❳•( ✮ the family of transition probabilities from ( to ❳.

The space ❍ ♥ ✿❂ ✭❑ ✂ | ✰ ✮ ♥ ✂ ❙ of admissible histories of the process at the ♥-th decision epoch, consists of sequences of states, decisions and sojourn times up to that epoch. At the initial epoch ❚ ✵ , the history consists of the initial state s ✵ ✷ ❙. At the first decision epoch ❚ ✶ , the two initial actions chosen by the players, the holding time at initial state and the new state are added to the initial state, and so on. A typical element of ❍ ♥ is therefore written as

❤ ♥ ❂ ✭s ✵ ❀ ❛ ✵ ❀ ❜ ✵ ❀ ✍ ✶ ❀ s ✶ ❀ ❛ ✶ ❀ ❜ ✶ ❀ ✍ ✷ ❀ ✿ ✿ ✿ ❀ s ♥ ✶ ❀ ❛ ♥ ✶ ❀ ❜ ♥ ✶ ❀ ✍ ♥ ❀ s ♥ ✮ ✿ A strategy for player 1 is a sequence ✙ ❂ ❢✙ ✵ ❀ ✙ ✶ ❀ ✙ ✷ ❀ ✿ ✿
✿❣ where ✙ ♥ is a probability measure on its action set ❆ s♥ , given the whole history ❤ ♥ up to time ♥. A Markov strategy (again for player 1) is a strategy of the form ✙ ❂ ❢❢ ✵ ❀ ❢ ✶ ❀ ❢ ✷ ❀ ✿ ✿ ✿❣, where each measure ❢ t is allowed to depend only on the current state s t and the stage parameter t. In particular, when each ❢ t is also independent on t, the strategy it is said stationary.

Formalizing the previous concepts, a strategy for player 1 (resp. player 2) is a sequence

✙ ❂ ❢✙ ♥ ❣ (resp. ✌ ❂ ❢✌ ♥ ❣) of stochastic kernels ✙ ♥ ✷ P✭❆•❍ ♥ ✮ (resp. ✌ ♥ ✷ P✭❇•❍ ♥ ✮), such that for every ❤ ♥ ✷ ❍ ♥ and ♥ ✷ ◆, ✙ ♥ ✭❆ s♥ •❤ ♥ ✮ ❂ ✶ (resp. ✌ ♥ ✭❇ s♥ •❤ ♥ ✮ ❂ ✶).

Inria

A strategy ✙ for player 1 is a Markov strategy (or Markov policy) if there exists a sequence

❢❢ ♥ ❣ of stochastic kernels ❢ ♥ ✷ P✭❆•❙✮ such that for every ♥ ✷ ◆, ❤ ♥ ✷ ❍ ♥ and ⑦ ❆ ✚ ❆ s♥ , ✙ ♥ ✭ ⑦ ❆•❤ ♥ ✮ ❂ ❢ ♥ ✭ ⑦ ❆•s ♥ ✮. Likewise for player 2: there exists ❢❣ ♥ ❣ such that ✌ ♥ ✭ ⑦ ❇•❤ ♥ ✮ ❂ ❣ ♥ ✭ ⑦ ❇•s ♥ ✮,
for all ⑦ ❇ ✚ ❇ s♥ . Here, ❢ ♥ ✭ ⑦ ❆•s ♥ ✮ represents the probability that player 1 chooses actions in ⑦ ❆, at stage ♥ in state s ♥ ; likewise for player 2 with ❣ ♥ ✭ ⑦ ❇•s ♥ ✮. We denote with ✆ (resp. ) the set of all Markov strategies of player 1 (resp. 2) and with some abuse of notation, we write ✙ ❂ ❢❢ ♥ ❣ and ✌ ❂ ❢❣ ♥ ❣.

For player 1, a Markov strategy ✙ ❂ ❢❢ ♥ ❣ is stationary if there exists ❢ ✷ P✭❆•❙✮ such that ❢✭s✮ ✷ P✭❆ s ✮ and ❢ ♥ ❂ ❢ for all s ✷ ❙ and ♥ ✷ ◆. In this case, we identify ✙ with ❢, i.e., ✙ ❂ ❢ ❂ ❢❢❀ ❢❀ ✿✿✿❣. We denote by ✆ st❛t the set of all stationary strategies for player

From here on, we make the following abuse of notation: for each s ✷ ❙ and given a pair of probability distributions ✘ and ✏ on ❆ s and ❇ s respectively, | ❆s | ❇s ❤✭s❀ ❛❀ ❜✮✏✭d❜✮✘✭d❛✮ whenever the integral is well defined, will be denoted by ❤✭s❀ ✘❀ ✏✮. Also, for a function ✣ defined on ❑, we note ✣✭s❀ ❢❀ ❣✮ instead of ✣✭s❀ ❢✭s✮❀ ❣✭s✮✮, for given stationary strategies ✭❢❀ ❣✮ ✷ ✆ st❛t ✂ st❛t .

In order to evaluate the performance of policies, we use a total discounted criterion. We assume that the rewards are continuously discounted, with a discount factor ☛. More precisely let, for ♥ ❂ ✶, s ✷ ❙, ✙ ✷ ✆ and ✌ ✷ , the expected ♥-stage ☛-discounted reward be defined as follows:

❱ ✙❀✌ ♥ ✭s✮ ✿❂ ❊ ✙❀✌ s ♥ ✶ ❳ ❦❂✵ ) ❚ ❦✰✶ ❚ ❦ ❡ ☛t ❵✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮dt ❂ ❊ ✙❀✌ s ♥ ✶ ❳ ❦❂✵ ❡ ☛❚ ❦ ✶ ❡ ☛✍ ❦✰✶ ☛ ❵✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✿
The infinite-horizon total expected ☛-discounted payoff is

❱ ✙❀✌ ✭s✮ ✿❂ ❊ ✙❀✌ s ✶ ❳ ❦❂✵ ❡ ☛❚ ❦ ✶ ❡ ☛✍ ❦✰✶ ☛ ❵✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✿ (3)
Alternatively, given a pair of policies ✙ and ✌, we can write its reward using the variables ☞ and ★ and obtain for the finite stage horizon and for the infinite horizon respectively,

❱ ✙❀✌ ✭s✮ ❂ ❊ s ✧ ✶ ❳ t❂✵ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ ★✭❙ t ❀ ❆ t ❀ ❇ t ✮❵✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ❱ ✙❀✌ ♥ ✭s✮ ❂ ❊ s ✧ ♥ ✶ ❳ t❂✵ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ ★✭❙ t ❀ ❆ t ❀ ❇ t ✮❵✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ❀
where we adopt the usual conventions that ◗ ✶ ❦❂✵ ❳ ❦ ❂ ✶ and P ✶ t❂✵ ( t ❂ ✵. Briefly, the first expression above comes from the following considerations.

❱ ✙❀✌ ✭s✮ ❂ ❊ ✙❀✌ s ✧ ✶ ❳ t❂✵ ) ❚t✰✍t✰✶ ❚t ❡ ☛✉ d✉ ❵✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ❂ ❊ ✙❀✌ s ✧ ✶ ❳ t❂✵ ❡ ☛❚t ✶ ❡ ☛✍t✰✶ ☛ ❵✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ❂ ❊ ✙❀✌ s ✧ ✶ ❳ t❂✵ ❡ ☛✭ P t ❦❂✵ ✍ ❦✮ ✶ ❡ ☛✍t✰✶ ☛ ❵✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ❂ ❊ ✙❀✌ s ✧ ✶ ❳ t❂✵ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ ★✭❙ t ❀ ❆ t ❀ ❇ t ✮❵✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ✿
Similarly, the second one can be justified.

At this point, observe that we can work with an instantaneous one-step reward functions r:

❑ ✦ | defined by r✭s❀ ❛❀ ❜✮ ❂ ★✭s❀ ❛❀ ❜✮❵✭s❀ ❛❀ ❜✮. We obtain the new expressions

❱ ✙❀✌ ✭s✮ ❂ ❊ ✙❀✌ s ✧ ✶ ❳ t❂✵ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ r✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ❀ (4)
❱ ✙❀✌ ♥ ✭s✮ ❂ ❊ ✙❀✌ s ✧ ♥ ✶ ❳ t❂✵ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ r✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ✿ (5)
We now state our working assumptions. A first set of "general" assumptions bears on the distribution probabilities of the holding time, the instantaneous reward function and the transition kernels.

Assumption 1.

(a) The state space ❙ is a Borel subset of a complete and separable metric space. (b) For each s ✷ ❙, the sets ❆ s and ❇ s are compact. (c) For each s ✷ ❙, and ❜ ✷ ❇ s , ❵✭s❀ ✁❀ ❜✮ is upper semi-continuous on ❆ s . (d) For each s ✷ ❙, and ❛ ✷ ❆ s , ❵✭s❀ ❛❀ ✁✮ is lower semi-continuous on ❇ s . (e) For each s ✷ ❙ and each bounded measurable function ✈ on ❙, the function The following result has been extracted from [START_REF] Luque-Vásquez | Zero-sum semi-Markov game in Borel spaces with discounted payoff[END_REF]Lemma 4.1].

✭❛❀ ❜✮ ✼ ✦ | ✈✭②✮◗✭d②•s❀ ❛❀ ❜✮ is continuous on ❆ s ✂ ❇ s . (f ) The function ✭s❀ ❛❀ ❜✮ ✼ ✦ | ✶ ✵ t❋ ✭dt•s❀ ❛❀ ❜✮ is continuous on ❑.
Proposition 2.1. If there exists a pair of positive numbers ✒ and ✎ such that

❋ ✭✒•s❀ ❛❀ ❜✮ ✺ ✶ ✎
for all ✭s❀ ❛❀ ❜✮ ✷ ❑, then Assumption 2 holds with ✚ ❂ ✶ ✎ ✰ ✎❡ ☛✒ .

Remark 2.2. The theory of SMDP can be found in [START_REF] Bhattacharya | Controlled semi-Markov models -the discounted case[END_REF] for the case of Borel state spaces, and in [START_REF] Ross | Applied Probability Models with Optimization Applications[END_REF] and [START_REF] Puterman | Markov Decision Processes[END_REF] for the case of discrete and finite state spaces, respectively. All these references work with Assumption 1 and with the assumption stated in Proposition 2.1, restricted to only one player.

Items (a)-(e) in Assumption 1 are those considered in [START_REF] Luque-Vásquez | Zero-sum semi-Markov game in Borel spaces with discounted payoff[END_REF]. Item (f), adopted from [START_REF] Jaśkiewicz | Approximations of noncooperative semi-Markov games[END_REF][START_REF] Jaśkiewicz | Stochastic Games with Unbounded Payoffs: Applications to Robust Control in Economics[END_REF],

replaces the more restrictive assumption presented in the first paper, which asks, for all t, for the continuity of ❋ ✭t•s❀ ❛❀ ❜✮ on ❑. This stronger assumption, restricted to one player, is also made in [START_REF] Bhattacharya | Controlled semi-Markov models -the discounted case[END_REF] and [START_REF] Vecchia | Rolling Horizon Procedure on Controlled Semi-Markov Models. The Discounted Case[END_REF] for the SMDP case. ☎ Let us denote with ▼✭❙✮ the space of measurable functions on ❙, and ▼ ✰ ✭❙✮ the subspace of nonnegative functions of ▼✭❙✮. On ▼ ✰ ✭❙✮, we define the operator ▲ which maps ✈ to ▲✈ in the following way: for s ✷ ❙,

✭▲✈✮✭s✮ ✿❂ s✉♣ ❛✷❆s❀❜✷❇s ) ❙ ✈✭③✮◗✭d③•s❀ ❛❀ ❜✮✿ Let ▲ ♥ ✈ ❂ ▲✭▲ ♥ ✶ ✈✮ for ♥ ✷ ◆, with ▲ ✵ ✈ ❂ ✈.
Clearly, ▲✭✕✈✮ ❂ ✕▲✭✈✮ for every positive scalar

✕.

We now state assumptions bearing on the cost function and the way it interacts with transition kernels.

Assumption 3. Let | ✿ ❙ ✼ ✦ | be defined by |✭s✮ ✿❂ ✶ ❳ t❂✵ ✚ t ✭▲ t r ✵ ✮✭s✮❀ where r ✵ ✭s✮ ❂ s✉♣ ❛✷❆s❀❜✷❇s •r✭s❀ ❛❀ ❜✮•. Assume |✭s✮ ❁ ✶❀ ✽s ✷ ❙. If ✖ ✷ ▼ ✰ ✭❙✮ is strictly positive, for ✈ ✷ ▼✭❙✮ we define the ✖-weighted norm ••✈•• ✖ ❂ s✉♣ s✷❙ •✈✭s✮•❂✖✭s✮. Assumption 4.
There exist a measurable function ✖ ✿ ❙ ✦ ❬✶❀ ✶✮ and a positive constant ♠ such that for all ✭s❀ ❛❀ ❜✮ ✷ ❑,

(a) •r✭s❀ ❛❀ ❜✮• ✺ ♠ ✖✭s✮, (b)
| ✖✭③✮◗✭d③•s❀ ❛❀ ❜✮ ✺ ✖✭s✮.

Assumption 5. There exists ▼ ❃ ✵ such that •r✭s❀ ❛❀ ❜✮• ✺ ▼ for all ✭s❀ ❛❀ ❜✮ ✷ ❑.

RR n°8019

Remark 2.3. An assumption similar to Assumption 3 appears in [START_REF] Bhattacharya | Controlled semi-Markov models -the discounted case[END_REF] for the SMDP case and in [START_REF] Hernández-Lerma | Value iteration and rolling plans for Markov control processes with unbounded rewards[END_REF] for the MDP case, both for a single player, while Assumption 4 could be associated to similar ones in [START_REF] Puterman | Markov Decision Processes[END_REF]Chapter 6] and in [6, Chapter 2], both of them for MDP. ☎ Remark 2.4. As a consequence of Assumption 4 (b), we have, for all s ✷ ❙ and all ✈ ✷ ▼✭❙ ✮,

☞ ☞ ☞ ☞ ) ❙ ✈✭③✮◗✭d③•s❀ ❛❀ ❜✮ ☞ ☞ ☞ ☞ ✺ ) ❙ •✈✭③✮• ✖✭③✮ ✖✭③✮◗✭d③•s❀ ❛❀ ❜✮ ✺ ••✈•• ✖ ) ❙ ✖✭③✮◗✭d③•s❀ ❛❀ ❜✮ ✺ ••✈•• ✖ ✖✭s✮ ✿ (6)
With the definition of r ✵ introduced in Assumption 3, Assumption 4 (a) can be written In [START_REF] Hernández-Lerma | Value iteration and rolling plans for Markov control processes with unbounded rewards[END_REF] and in [7, Proposition 4.3.1., p. 53], it is shown that Assumption 4 implies Assumption 3 for the case of MDP. A similar argument is valid for SMGs. Indeed, with (6), ❑ into ✭✵❀ ✶✮ (continuity is required for satisfying Assumption 1 (f )). The process ❢❙ t ❣ turns out to be a Markov process when ✭✙❀ ✌✮ is a pair of Markov policies, and a time-homogeneous Markov process when ✭✙❀ ✌✮ is a pair of stationary policies.

••r ✵ •• ✖ ✺ ♠.
•✭▲ t r ✵ ✮✭s✮• ❂ ☞ ☞ ☞ ☞ ☞ s✉♣ ❛✷❆s❀❜✷❇s ) ❙ ✭▲ t ✶ r ✵ ✮✭③✮◗✭d③•s❀ ❛❀ ❜✮ ☞ ☞ ☞ ☞ ☞ ✺ s✉♣ ❛✷❆s❀❜✷❇s ☞ ☞ ☞ ☞ ) ❙ ✭▲ t ✶ r ✵ ✮✭③✮◗✭d③•s❀ ❛❀ ❜✮ ☞ ☞ ☞ ☞ ✺ ••▲ t ✶ r ✵ •• ✖ ✖✭s✮ ❀ for all t ❂ ✶. By induction, for any t, ••▲ t r ✵ •• ✖ ✺ ••▲ t ✶ r ✵ •• ✖ ✺ ✁ ✁ ✁ ✺ ••r ✵ •• ✖ ✺ ♠ and then ••|•• ✖ ✺ ♠ ✶ ✚ , or | ✺ ♠ ✶ ✚ ✖,

☎ 3 Performance Criterion and Related Results

Under suitable hypotheses, in this section we characterize the value function for the finite and infinite-horizon games and the strategies which produce the equilibria through operators defined in ( 9) and ( 10) below. We also analyze the convergence of the values for the finite-horizon games to that of the infinite-horizon one. These results will be used to prove the convergence of RH and ARH procedures described in the next section.

The lower and the upper value functions of the infinite-horizon game are defined, as usual, for s ✷ ❙ , as

❱ ✄ ✭s✮ ❂ s✉♣ ✙✷✆ ✐♥❢ ✌✷ ❱ ✙❀✌ ✭s✮ and ❱ ✄ ❂ ✐♥❢ ✌✷ s✉♣ ✙✷✆ ❱ ✙❀✌ ✭s✮ (7)
Inria respectively. We know that, in general, ❱ ✄ ✺ ❱ ✄ .

If ❱ ✄ ❂ ❱ ✄ , and both the "sup inf" and "inf sup" are attained, we refer to this common value as the value of the game, and we note it with ❱ ✄ (we refer to [START_REF] Nowak | On zero-sum stochastic games with general state space, I[END_REF] for definitions on general dynamic zero-sum games). Likewise for the finite-horizon games. Suppose that our games have a value. Then, the objective of the players is to find (when it exists) a pair of policies that solves, given the current state s:

✭✙ ✄ ✭s✮❀ ✌ ✄ ✭s✮✮ ✷ ❛r❣ ♠❛① ✙ ♠✐♥ ✌ ❱ ✙❀✌ ✭s✮✿ (8)
Such a pair of strategies ✭✙ ✄ ❀ ✌ ✄ ✮ ✷ ✆ ✂ is said to be an equilibrium.

With |✭✁✮ being defined in Assumption 3, we denote

• | ❂ ❢✈ ✷ ▼✭❙✮ ✿ •✈✭s✮• ✺ |✭s✮ for all s ✷ ❙❣; • ▼ ✖ ✭❙✮ the
✈ ✷ |, •❚✈✭s✮• ✺ r ✵ ✭s✮ ✰ ✚✭▲•✈•✮✭s✮ ✺ r ✵ ✭s✮ ✰ ✚▲|✭s✮ ❂ |✭s✮❀ which implies ❚ ✈ ✷ |.
On the other hand, under Assumption 4, we can use [START_REF] Hernández-Lerma | Adaptive Markov Control Processes[END_REF] in [START_REF] Kwon | Receding Horizon Control. Predictive Control for State Models[END_REF]

to obtain ••❚✈•• ✖ ✺ ♠ ✰ ✚••✈•• ✖ , which implies in turn that ❚ ✈ ✷ ▼ ✖ ✭❙✮.
The following results provide the existence of optimal stationary strategies, then bounds and convergence results related to the operator ▲. First, under Assumptions 1, 2 and 3, the s✉♣ ✐♥❢ and ✐♥❢ s✉♣ are attained in [START_REF] Jaśkiewicz | Stochastic Games with Unbounded Payoffs: Applications to Robust Control in Economics[END_REF] for each s ✷ ❙. Lemma 3.2. Under Assumptions 1, 2 and 3, for each ✈ ✷ | there exist stationary strategies

⑦ ❢ ✷ ✆ st❛t , ⑦ ❣ ✷ st❛t such that ✭❚ ✈✮✭s✮ ❂ r✭s❀ ⑦ ❢❀ ⑦ ❣✮ ✰ ☞✭s❀ ⑦ ❢❀ ⑦ ❣✮ ) ❙ ✈✭③✮◗✭d③•s❀ ⑦ ❢❀ ⑦ ❣✮ ❂ s✉♣ ❢✷✆st❛t ✚ r✭s❀ ❢❀ ⑦ ❣✮ ✰ ☞✭s❀ ❢❀ ⑦ ❣✮ ) ❙ ✈✭③✮◗✭d③•s❀ ❢❀ ⑦ ❣✮ ✛ (11) ❂ ✐♥❢ ❣✷ st❛t ✚ r✭s❀ ⑦ ❢❀ ❣✮ ✰ ☞✭s❀ ⑦ ❢❀ ❣✮ ) ❙ ✈✭③✮◗✭d③•s❀ ⑦ ❢❀ ❣✮ ✛ ✿ Proof. According to Lemma 3.1, for each ✈ ✷ |, ❚ ✈ ✷ |.
The proof makes use of well-known measurable selection theorems and is similar to that of Lemma 5.1 in [START_REF] Luque-Vásquez | Zero-sum semi-Markov game in Borel spaces with discounted payoff[END_REF], but with the weaker Assumption 1 (f ), which is enough to guarantee the existence of the pair of policies stated.

Lemma 3.3. Suppose that Assumptions 1, 2 and 3 hold. Then, for all s ✷ ❙, ✙ ✷ ✆, ✌ ✷ , ✈ ✷ | and t ✷ ◆, we have:

(a) ❊ ✙❀✌ s ❬✈✭❙ t ✮( ✺ ✭▲ t ✈✮✭s✮✿ (12)
(b)

•✐♠ ♥✦✶ ❊ ✙❀✌ s ✧✥ ♥ ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ ✈✭❙ ♥ ✮ ★ ❂ ✵✿ (13)
Proof. We prove (a) by induction on t. Consider the policies ✙ ❂ ❢❢ ✵ ❀ ❢ ✶ ❀ ✿ ✿ ✿❣ and ✌ ❂ ❢❣ ✵ ❀ ❣ ✶ ❀ ✿ ✿ ✿❣.

Since we are dealing with Markov policies ✙ ✷ ✆ and ✌ ✷ , by [6, Properties 2.5 e and f, pp. 5-6],

we have

❊ ✙❀✌ s ❬✈✭❙ t✰✶ ✮•❙ ✵ ❂ s❀ ❆ ✵ ❂ ❛❀ ❇ ✵ ❂ ❜❀ ❙ ✶ ❂ ③( ❂ ❊ ✙ ✵ ❀✌ ✵ ③ ❬✈✭❙ t ✮( (14)
where we denote with ✙ ✵ ❂ ❢❢ ✵

✵ ❀ ❢ ✵ ✶ ❀ ✿✿✿❣ and ✌ ✵ ❂ ❢❣ ✵ ✵ ❀ ❣ ✵ ✶ ❀ ✿ ✿ ✿❣ the shifted policies defined by ❢ ✵ t ❂ ❢ t✰✶ and ❣ ✵ t ❂ ❣ t✰✶ . For t ❂ ✵ the result is obvious. For t ❂ ✶, since | ❙ ✈✭③✮◗✭d③•s❀ ❛❀ ❜✮ ✺ ✭▲✈✮✭s✮, ❊ ✙❀✌ s ❬✈✭❙ ✶ ✮( ❂ ) ❆ ) ❇ ) ❙ ✈✭③✮◗✭d③•s❀ ❛❀ ❜✮❣ ✵ ✭d❜✮❢ ✵ ✭d❛✮ ✺ ✭▲✈✮✭s✮✿
In general, using [START_REF] Puterman | Markov Decision Processes[END_REF], we have for any t:

❊ ✙❀✌ s ❬✈✭❙ t✰✶ ✮( ❂ ) ❆ ) ❇ ) ❙ ❊ ✙❀✌ ❬✈✭❙ t✰✶ ✮•❙ ✵ ❂ s❀ ❆ ✵ ❂ ❛❀ ❇ ✵ ❂ ❜❀ ❙ ✶ ❂ ③( ◗✭d③•s❀ ❛❀ ❜✮❣ ✵ ✭d❜✮❢ ✵ ✭d❛✮ ❂ ) ❆ ) ❇ ) ❙ ❊ ✙ ✵ ❀✌ ✵ ③ ❬✈✭❙ t ✮(◗✭d③•s❀ ❛❀ ❜✮❣ ✵ ✵ ✭d❜✮❢ ✵ ✵ ✭d❛✮ ✺ ) ❆ ) ❇ ) ❙ ✭▲ t ✈✮✭③✮◗✭d③•s❀ ❛❀ ❜✮❣ ✵ ✵ ✭d❜✮❢ ✵ ✵ ✭d❛✮ ✺ ✭▲ t✰✶ ✈✮✭s✮✿
For the proof of (b), we have:

❊ ✙❀✌ s ✧✥ ♥ ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ ✈✭❙ ♥ ✮ ★ ✺ ✚ ♥ ❊ ✙❀✌ s ✈✭❙ ♥ ✮ ✺ ✚ ♥ ✭▲ ♥ ✈✮✭s✮ ✺ ✚ ♥ ✭▲ ♥ |✮✭s✮ ❂ ✶ ❳ t❂♥ ✚ t ✭▲ t r ✵ ✮✭s✮ ✦ ✵❀ as ♥ ✦ ✶, by Assumption 3.
The next result generalizes Theorems 4.3 and 4.4 from [START_REF] Luque-Vásquez | Zero-sum semi-Markov game in Borel spaces with discounted payoff[END_REF], proved under the more restrictive Assumption 1 (see Remark 2.2), and Assumptions 2 and 4. (c) The infinite-horizon game has a value, and

Inria

•❱ ✄ ❱ ✄ ♥ • ✺ P ✶ t❂♥ ✚ t ▲ t r ✵ ❂ ✚ ♥ ▲ ♥ | ✦ ✵ (pointwise) as ♥ ✦ ✶. (d) ❱ ✄ is the function in | satisfying the optimality equation ❚ ❱ ✄ ❂ ❱ ✄ . Moreover,
there exists a pair of stationary policies ✭❢ ✄ ❀ ❣ ✄ ✮ which is an equilibrium pair for the infinite- horizon game.

(e) In addition, if Assumption 4 holds, ❚ is a contractive operator on ▼ ✖ ✭❙✮ of modulus ✚ and

••❱ ✄ ❱ ✄ ♥ •• ✖ ✺ ♠✚ ♥ ✶ ✚ .
Proof. (a) By definition of r ✵ , for all ✭s❀ ❛❀ ❜✮ ✷ ❑, •r✭s❀ ❛❀ ❜✮• ✺ r ✵ ✭s✮, and taking ✈ ❂ r ✵ in Lemma 3.3 (a), for all t ✷ ◆,

❊ ✙❀✌ s •r✭❙ t ❀ ❆ t ❀ ❇ t ✮• ✺ ❊ ✙❀✌ s •r ✵ ✭❙ t ✮• ✺ ✭▲ t r ✵ ✮✭s✮❀ which implies •❱ ✙❀✌ ✭s✮• ✺ ✶ ❳ t❂✵ ✚ t ✭❊ ✙❀✌ s •r✭❙ t ❀ ❆ t ❀ ❇ t ✮•✮ ✺ ✶ ❳ t❂✵ ✚ t ✭▲ t r ✵ ✮✭s✮ ❂ |✭s✮ and therefore •❱ ✭s✮• ✺ |✭s✮❀ •❱ ✭s✮• ✺ |✭s✮✿ (b)
The main ideas of the proof can be sketched out as follows. By backward induction and well-known arguments, it is possible to prove that starting from ❱ ✄ ✵ ✑ ✵ ✷ |, after ♥ successive applications of the operator ❚ , we obtain the value function of the game as well as the equilibrium strategies. In this recursive application it is crucial taking in mind that Assumption 3 implies that ❚ maps | into itself (Lemma 3.1). In this way, for each ❦ ✺ ♥, ❱ ✄

❦ is in the domain of ❚ , |. (c) For any s ✷ ❙, ✙ ✷ ✆ and ✌ ✷ , consider formulas (4) and ( 5) for ❱ ✙❀✌ ✭s✮ and ❱ ✙❀✌ ♥ ✭s✮.

Then, using Lemma 3.3 (a) again,

•❱ ✙❀✌ ✭s✮ ❱ ✙❀✌ ♥ ✭s✮• ✺ ✶ ❳ t❂♥ ✚ t ❊ ✙❀✌ s •r✭❙ t ❀ ❆ t ❀ ❇ t ✮• ✺ ✶ ❳ t❂♥ ✚ t ✭▲ t r ✵ ✮✭s✮✿ (15)
In addition, according to Lemma A.2 in the Appendix,

•❱ ✄ ✭s✮ ❱ ✄ ♥ ✭s✮• ❂ ☞ ☞ ☞ ☞ ✐♥❢ ✌ s✉♣ ✙ ❱ ✙❀✌ ✭s✮ ✐♥❢ ✌ s✉♣ ✙ ❱ ✙❀✌ ♥ ✭s✮ ☞ ☞ ☞ ☞ ✺ s✉♣ ✙ s✉♣ ✌ •❱ ✙❀✌ ✭s✮ ❱ ✙❀✌ ♥ ✭s✮• ✿ RR n°8019
Then using [START_REF] Ross | Applied Probability Models with Optimization Applications[END_REF],

•❱ ✄ ✭s✮ ❱ ✄ ♥ ✭s✮• ✺ ✶ ❳ t❂♥ ✚ t ✭▲ t r ✵ ✮✭s✮✿ Likewise, •❱ ✄ ✭s✮ ❱ ✄ ♥ ✭s✮• ✺ s✉♣ ✙ s✉♣ ✌ •❱ ✙❀✌ ✭s✮ ❱ ✙❀✌ ♥ ✭s✮• ✺ ✶ ❳ t❂♥ ✚ t ✭▲ t r ✵ ✮✭s✮✿
From part (b) we know that each finite-stage game has a value (and then ❱ ✄ ♥ ✭s✮ ❂ ❱ ✄ ♥ ✭s✮ ❂ ❱ ✄ ♥ ✭s✮), and taking into account the fact that Assumption 3 implies P ✶ t❂♥ ✚ t t r ✵ ✮✭s✮ ✦ ✵ as ♥ ✦ ✶, we have that the infinite-horizon game has a value, which verifies

❱ ✄ ✭s✮ ❂ •✐♠ ♥✦✶ ❱ ✄ ♥ ✭s✮❀
with the convergence bound

•❱ ✄ ✭s✮ ❱ ✄ ♥ ✭s✮• ✺ ✶ ❳ t❂♥ ✚ t ✭▲ t r ✵ ✮✭s✮ ❂ ✚ ♥ ✭▲ ♥ |✮✭s✮ ✿ (16)
(d) First, we will prove uniqueness. That is, that there is at most one ❱ ✷ | such that ❚ ❱ ❂ ❱ . For this, observe that Lemma A.2 implies the following inequality for any pair of functions ✉ and ✈ in |, and for any s ✷ ❙, Lemma 3.3 (b). This implies the uniqueness of fixed points in |.

•✭❚✉ ❚ ✈✮✭s✮• ✺ ✚ s✉♣ ❛✷❆s❀❜✷❇s ) ❙ •✉✭③✮ ✈✭③✮•◗✭d③•s❀ ❛❀ ❜✮ ❂ ✚✭▲•✉ ✈•✮✭s✮ ✿ In general, for ♥ ✷ ◆, •✭❚ ♥ ✉ ❚ ♥ ✈✮✭s✮• ✺ ✚ ♥ ✭▲ ♥ •✉ ✈•✮✭s✮ ✺ ✷✚ ♥ ✭▲ ♥ |✮✭s✮ ✦ ✵❀ as in
The identity ❚ ❱ ✄ ❂ ❱ ✄ follows by parts (b) and (c) and the uniqueness already shown. Indeed, as ♥ ✦ ✶,

❚ ♥ ✵ ❂ ❱ ✄ ♥ ✦ ❱ ✄ ❀
and it results that ❚ ❱ ✄ ❂ ❱ ✄ . Morover, since by parts (a) and (c), ❱ ✄ ❂ ❱ ✄ ✷ |, applying Lemma 3.2, there exists a pair ✭❢ ✄ ❀ ❣ ✄ ✮ ✷ ✆ st❛t ✂ st❛t of stationary strategies such that ❚ ❱ ✄ ❂ ❚ ❢ ✄ ❀❣ ✄ ❱ ✄ . In consequence ❱ ✄ is a fixed point of ❚ ❢ ✄ ❀❣ ✄ , resulting, by Lemma 3.4, in

❱ ✄ ❂ ❱ ❢ ✄ ❀❣ ✄ ✿ (e)
The contractivity is a direct consequence of (4).

For the second part, observe that from [START_REF] Sethi | A Theory of Rolling Horizon Decision Making[END_REF]

, •❱ ✄ ✭s✮ ❱ ✄ ♥ ✭s✮• ✺ P ✶ t❂♥ ✚ t ✭▲ t r ✵ ✮✭s✮. By using Remark 2.4, ✶ ❳ t❂♥ ✚ t ✂ ✭▲ t r ✵ ✮ ✺ ✶ ❳ t❂♥ ✚ t ✂ ♠✖ ❂ ♠✚ ♥ ✶ ✚ ✖ ❀ which gives ••❱ ✄ ❱ ✄ ♥ •• ✖ ✺ ♠✚ ♥ ✶ ✚ ✿ Inria
Observe that the contractivity of ❚ (claim (e)) is proved in [11, Lemma 6.1] under a stronger assumption than our Assumption 1 (f).

Lemma 3.4. Suppose that Assumptions 1, 2 and 3 hold. Then, given a pair of stationary policies ❢ ✷ ✆ st❛t and ❣ ✷ st❛t , the value ❱ ❢❀❣ is the unique fixed point of ❚ ❢❀❣ . Proof. The proof of the fixed point equation follows from the next calculations, for s ✷ ❙,

❱ ❢❀❣ ✭s✮ ❂ ❊ ❢❀❣ s ✧ ✶ ❳ t❂✵ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ r✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ❂ ❊ ❢❀❣ s ✧ r✭s❀ ❢❀ ❣✮ ✰ ✶ ❳ t❂✶ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ r✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ❂ r✭s❀ ❢❀ ❣✮ ✰ ☞✭s❀ ❢❀ ❣✮ ❊ ❢❀❣ s ✧ ✶ ❳ t❂✶ ✥ t ✶ ( ❦❂✶ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ r✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ❂ r✭s❀ ❢❀ ❣✮ ✰ ☞✭s❀ ❢❀ ❣✮ ) ❙ ❱ ❢❀❣ ✭③✮◗✭d③•s❀ ❢❀ ❣✮ ❂ ✭❚ ❢❀❣ ❱ ❢❀❣ ✮✭s✮ ✿
The uniqueness follows similarly to the first part in the proof of Theorem 3.1 part (d).

4 Approximation Procedures

Rolling Horizon Procedure

For a wide class of stochastic control or game problems, obtaining an optimal policy explicitly is a difficult task. This is why practitioners often use instead a heuristic method called the Rolling Horizon procedure (also, Receding Horizon, or Model Predictive Control), which works as follows. To the infinite-horizon game is associated a finite-stage horizon1 game: for a given integer ◆ (the stage-horizon length) and a state s, find:

✭❋ ❍P ✮ s✉♣ ✙ ✐♥❢ ✌ ❊ ✙❀✌ s ✧ ◆ ✶ ❳ t❂✵ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ r✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ✿
Solving this problem for each initial state results in a sequence of pairs of Markovian policies

✙ ✄ ◆ ❂ ✭❢ ◆ ❀ ❢ ◆ ✶ ❀ ✿ ✿ ✿ ❀ ❢ ✷ ❀ ❢ ✶ ✮❀ ✌ ✄ ◆ ❂ ✭❣ ◆ ❀ ❣ ◆ ✶ ❀ ✿ ✿ ✿ ❀ ❣ ✷ ❀ ❣ ✶ ✮❀ (17)
where ❢ ✶ ✭s ◆ ✶ ✮ is the best action to be applied at stage t ❂ ◆ ✶ by the first player, and ❣ ✶ ✭s ◆ ✶ ✮ for the second one, when only one stage remains to reach the horizon, ❢ ✷ and ❣ ✷ are the best decision rules to be applied for the players when two stages remain to reach the horizon, at time t ❂ ◆ ✷, and so on. In particular, ❢ ◆ ✭s ✵ ✮ and ❣ ◆ ✭s ✵ ✮ are the best decision rules to be applied to the initial state s ✵ .

The RH method prescribes to repeatedly solve such a finite-stage horizon problem, taking the current state as initial state. Then, only the first decision will be applied.

Specifically, the procedure to construct a RH policy is the following one. Fix some integer ◆ and consider a denumerable set of epochs. The RH procedure does not specify how to compute the values ❢ ◆ ✭s t ✮ and ❣ ◆ ✭s t ✮. Its efficiency is based on the idea that computing ❢ ◆ ✭s t ✮ and ❣ ◆ ✭s t ✮ alone is usually much easier than computing the ◆ decision rules in (17). On the other hand, the performance of the resulting sequence of decisions is not the optimal one, although the intuition is that when ◆ is "large enough", the performance should be close to the optimal. The practical issue is then to choose ◆ so as to obtain a proper compromise between precision and the computational effort needed to obtain ❢ ◆ ✭s t ✮ and ❣ ◆ ✭s t ✮. We address this issue through two formal qualitative and quantitative questions. Let ❯ ◆ ✭s✮ be the expected gain achieved by player 1 with the RH procedure with horizon length ◆ , starting in state s:

Q1 Under which conditions on the problem is it true that •✐♠ ◆ ✦✶ ❯ ◆ ✭s✮ ❂ ❱ ✄ ✭s✮?

Q2 Given a state s and ✎ ❃ ✵, is it possible to compute ◆ such that •❯ ◆ ✭s✮ ❱ ✄ ✭s✮• ❁ ✎?
In what follows we prove the convergence of the procedure to the value of the original game, thereby answering question Q1. We obtain convergence bounds that can be used to answer Q2. The term "convergence" has to be understood in the sense that when the horizon ◆ goes to infinity, the value obtained with the procedure approaches the value of the game. The preliminary observation, classical for studying Rolling Horizon, is that the procedure RH effectively implements, for both players, a stationary Markov policy. Since player 1 will repeatedly play according to the state-feedback function ❢ ◆ , and player 2 will play ❣ ◆ , we have ❯ ◆ ❂ ❱ ❢ ◆ ❀❣ ◆ . We begin with a technical lemma of general interest. Lemma 4.1. Suppose that Assumption 3 holds. Let ✭❢❀ ❣✮ ✷ ✆ st❛t ✂ st❛t be a pair of stationary strategies, with total discounted reward ❱ ❢❀❣ , and let ✈ ✷ | and ✇ ❂ ✵ be such that

✈ ✺ ❚ ❢❀❣ ✈ ✰ ✇ ✿ Then, for any ♥ ✷ ◆, ✭❚ ❢❀❣ ✮ ♥ ✈ ✺ ❱ ❢❀❣ ✰ ✶ ❳ t❂♥ ✚ t ✂ ▲ t ✇ ✿ Similarly, if ✈ ❂ ❚ ❢❀❣ ✈ ✇❀ then ✭❚ ❢❀❣ ✮ ♥ ✈ ❂ ❱ ❢❀❣ ✶ ❳ t❂♥ ✚ t ✂ ▲ t ✇ ✿ Combining both inequalities: if •✈ ❚ ❢❀❣ ✈• ✺ ✇, then for any ♥ ✷ ◆, ☞ ☞ ✭❚ ❢❀❣ ✮ ♥ ✈ ❱ ❢❀❣ ☞ ☞ ✺ ✶ ❳ t❂♥ ✚ t ✂ ▲ t ✇ ✿ (18)

Inria

Proof. First of all, we have from [START_REF] Kwon | Receding Horizon Control. Predictive Control for State Models[END_REF] and any function ✉ ✷ ▼✭❙✮,

✭❚ ❢❀❣ ✭✈ ✰ ✉✮✮✭s✮ ❂ r✭s❀ ❢❀ ❣✮ ✰ ☞✭s❀ ❢❀ ❣✮ ) ❙ ✈✭③✮◗✭d③•s❀ ❢❀ ❣✮ ✰ ☞✭s❀ ❢❀ ❣✮ ) ❙ ✉✭③✮◗✭d③•s❀ ❢❀ ❣✮ ❂ ✭❚ ❢❀❣ ✈✮✭s✮ ✰ ☞✭s❀ ❢❀ ❣✮ ) ❙ ✉✭③✮◗✭d③•s❀ ❢❀ ❣✮ ✺ ✭❚ ❢❀❣ ✈✮✭s✮ ✰ ☞✭s❀ ❢❀ ❣✮ ✂ ✭▲•✉•✮✭s✮ ✿
Also, in particular if ✇ ❂ ✵ (which implies ▲✇ ❂ ✵), we have:

❚ ❢❀❣ ✭✈ ✰ ✇✮ ✺ ❚ ❢❀❣ ✈ ✰ ✚ ✂ ▲✇ ✿
Then, we have successively:

✈ ✺ ❚ ❢❀❣ ✈ ✰ ✇ ❚ ❢❀❣ ✈ ✺ ✭❚ ❢❀❣ ✮ ✷ ✈ ✰ ✚ ✂ ▲✇
and by recurrence, it is clear that for all t: ✭❚ ❢❀❣ ✮ t ✈ ✺ ✭❚ ❢❀❣ ✮ t✰✶ ✈ ✰ ✚ t ✂ ▲ t ✇ ✿ Summing up these inequalities for t from ♥ to ♠, we obtain:

✭❚ ❢❀❣ ✮ ♥ ✈ ✺ ✭❚ ❢❀❣ ✮ ♠✰✶ ✈ ✰ ♠ ❳ t❂♥ ✚ t ✂ ▲ t ✇ ✿ (19)
As ♠ ✦ ✶, ✭❚ ❢❀❣ ✮ ♠ ✈ ✦ ❱ ❢❀❣ . To see that let us analyze the r.h.s. of the expression (easily derived by recurrence):

✭❚ ❢❀❣ ✮ ♠ ✈ ❂ ❊ ❢❀❣ ✧ ♠ ✶ ❳ t❂✵ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❢❀ ❣✮ ✦ r✭❙ t ❀ ❢❀ ❣✮ ★ ✰ ❊ ❢❀❣ ✧✥ ♠ ✶ ( t❂✵ ☞✭❙ t ❀ ❢❀ ❣✮ ✦ ✈✭❙ ♠ ✮ ★ ✿
The first term converges to the value ❱ ❢❀❣ by definition. For the second one, note that

❊ ❢❀❣ s ✧ ♠ ✶ ( t❂✵ ☞✭❙ t ❀ ❢❀ ❣✮✈✭❙ ♠ ✮ ★ ❂ ❊ ❢❀❣ s ✧ ♠ ✶ ( t❂✵ ☞✭❙ t ❀ ❆ t ❀ ❇ t ✮✈✭❙ ♠ ✮ ★ ✦ ✵ according to Lemma 3.3 (b).
The second term in ( 19) is a series of positive terms which either diverges, or converges to P ✶ t❂♥ ✚ t ✂ ▲ t ✇ ❁ ✶. In both cases, the bound follows.

The opposite inequality in the statement of the lemma follows similarly.

Theorem 4.1. Suppose that Assumptions 1, 2 and 3 hold. Then,

•❱ ✄ ❯ ◆ • ✺ ✷✚ ◆ ✂ ▲ ◆ | ✿ Proof.
By definition of an optimal ◆ ✶-stage strategy and the definition ( 5), for all s ✷ ❙ and

◆ ❂ ✶, ❱ ✄ ◆ ✶ ✭s✮ ❂ s✉♣ ✙ ✐♥❢ ✌ ❊ ✙❀✌ s ✧ ◆ ✷ ❳ t❂✵ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ r✭❙ t ❀ ❆ t ❀ ❇ t ✮ ★ ✿
If we add and subtract the term

✁ ✿❂ ✥ ◆ ✷ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ r✭❙ ◆ ✶ ❀ ❆ ◆ ✶ ❀ ❇ ◆ ✶ ✮ ❀ we obtain ❱ ✄ ◆ ✶ ✭s✮ ❂ s✉♣ ✙ ✐♥❢ ✌ ❊ ✙❀✌ s ✔ ◆ ✶ ❳ t❂✵ ✥ t ✶ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ r✭❙ t ❀ ❆ t ❀ ❇ t ✮ ✁ ✕ ❂ s✉♣ ✙ ✐♥❢ ✌ ❊ ✙❀✌ s ❬❤ ✁( ✿ Applying Lemma A.
2 with ❢ ❂ ❊ ✙❀✌ s ❬❤ ✁( and ❣ ❂ ❊ ✙❀✌ s ❬❤(, we have:

☞ ☞ ☞ ☞ s✉♣ ✙ ✐♥❢ ✌ ❊ ✙❀✌ s ❬❤ ✁( s✉♣ ✙ ✐♥❢ ✌ ❊ ✙❀✌ s ❬❤( ☞ ☞ ☞ ☞ ✔ s✉♣ ✙ s✉♣ ✌ ❊ ✙❀✌ s •✁• ✿ Then, recognizing that ❱ ✄ ◆ ✭s✮ is s✉♣ ✙ ✐♥❢ ✌ ❊ ✙❀✌ s ❬❤(, we obtain: •❱ ✄ ◆ ✭s✮ ❱ ✄ ◆ ✶ ✭s✮• ✺ s✉♣ ✙ s✉♣ ✌ ❊ ✙❀✌ s ☞ ☞ ☞ ☞ ☞ ✥ ◆ ✷ ( ❦❂✵ ☞✭❙ ❦ ❀ ❆ ❦ ❀ ❇ ❦ ✮ ✦ r✭❙ ◆ ✶ ❀ ❆ ◆ ✶ ❀ ❇ ◆ ✶ ✮ ☞ ☞ ☞ ☞ ☞ ✿
Since for all ✭s❀ ❛❀ ❜✮ ✷ ❑, r✭s❀ ❛❀ ❜✮ ✺ r ✵ ✭s✮ by Assumption 3, and since ☞✭s❀ ❛❀ ❜✮ ✺ ✚, we further obtain:

•❱ ✄ ◆ ✭s✮ ❱ ✄ ◆ ✶ ✭s✮• ✺ s✉♣ ✙ s✉♣ ✌ ✚ ◆ ✶ ❊ ✙❀✌ s ❬r ✵ ✭❙ ◆ ✶ ✮( ✿ With Lemma 3.3 (a), ❊ ✙❀✌ s ❬r ✵ ✭❙ ◆ ✶ ✮( ✺ ✭▲ ◆ ✶
r ✵ ✮✭s✮, and we conclude:

•❱ ✄ ◆ ❱ ✄ ◆ ✶ • ✺ ✚ ◆ ✶ ✂ ▲ ◆ ✶ r ✵ ✿ (20)
Let us work with the inequality

❱ ✄ ◆ ✶ ✺ ❱ ✄ ◆ ✰ ✚ ◆ ✶ ✂ ▲ ◆ ✶ r ✵ ✿ Considering Theorem 3.1, part (b), ❱ ✄ ◆ ❂ ❚ ❢ ◆ ❀❣ ◆ ❱ ✄ ◆ ✶ , that is: ❱ ✄ ◆ ✭s✮ ❂ r✭s❀ ❢ ◆ ❀ ❣ ◆ ✮ ✰ ☞✭s❀ ❢ ◆ ❀ ❣ ◆ ✮ ✂ ) ❙ ❱ ✄ ◆ ✶ ✭③✮◗✭d③•s❀ ❢ ◆ ❀ ❣ ◆ ✮ ✺ r✭s❀ ❢ ◆ ❀ ❣ ◆ ✮ ✰ ☞✭s❀ ❢ ◆ ❀ ❣ ◆ ✮ ✂ ) ❙ ❱ ✄ ◆ ✭③✮◗✭d③•s❀ ❢ ◆ ❀ ❣ ◆ ✮ ✰ ✚ ◆ ✂ ▲ ◆ r ✵ ✭s✮ ❀
or in other words:

❱ ✄ ◆ ✺ ❚ ❢ ◆ ❀❣ ◆ ❱ ✄ ◆ ✰ ✚ ◆ ✂ ▲ ◆ r ✵ ✿ (21)
Using (18) in Lemma 4.1 with ❢ ✑ ❢ ◆ , ❣ ✑ ❣ ◆ , ♥ ❂ ✵ and ✇ ❂ ✚ ◆ ▲ ◆ r ✵ (which is effectively positive), we obtain since ❱ ❢ ◆ ❀❣ ◆ ❂ ❯ ◆ :

•❱ ✄ ◆ ❯ ◆ • ✺ ✶ ❳ t❂◆ ✚ t ✂ ▲ t r ✵ ✿ (22)
Finally, using Theorem 3.1 (c), Observe that this is the case, for instance, when the reward function r is positive.

•❱ ✄ ❯ ◆ • ✺ •❱ ✄ ❱ ✄ ◆ • ✰ •❱ ✄ ◆ ❯ ◆ • ✺ ✚ ◆ ✂ ▲ ◆ | ✰ ✚ ◆ ✂ ▲ ◆ | ❂ ✷✚ ◆ ✂ ▲ ◆ | ✿ Inria
✵ ✺ ❯ ◆ ❱ ✄ ◆ ✺ ✚ ◆ ✂ ▲ ◆ | ❀ or equivalently, ✚ ◆ ✂ ▲ ◆ | ✺ ❱ ✄ ◆ ❯ ◆ ✺ ✵ ✿ Moreover, since the sequence ❢❱ ✄
♥ ❣ ♥ is monotone by Proposition 4.1, we have ❱ ✄ ◆ ✺ ❱ ✄ . Accordingly, ( 16) can be refined into:

✵ ✺ ❱ ✄ ❱ ✄ ◆ ✺ ✚ ◆ ✂ ▲ ◆ | ✿
Combining the last inequalities, we get

✚ ◆ ✂ ▲ ◆ | ✺ ❱ ✄ ❯ ◆ ✺ ✚ ◆ ✂ ▲ ◆ | ❀
which is equivalent to the bound we look for.

Corollary 4.2. Suppose that Assumptions 1, 2 and 4 hold. Then,

•❱ ✄ ❯ ◆ • ✺ ✷♠✚ ◆ ✶ ✚ ✖❀ and therefore ••❱ ✄ ❯ ◆ •• ✖ ✺ ✷♠✚ ◆ ✶ ✚ ✿
If in addition Assumption 6 holds, then

••❱ ✄ ❯ ◆ •• ✖ ✺ ♠✚ ◆ ✶ ✚ ✿
Proof. If Assumption 4 holds, then (see Remark 2.4), ••▲ t r ✵ •• ✖ ✺ ♠ for all t, so that ✚ ◆ ▲ ◆ | ❂ P ✶ t❂◆ ✚ t ▲ t r ✵ ✔ P ✶ t❂◆ ♠✚ t ✖ ❂ ♠✚ ◆ ✶ ✚ ✖. The bounds follow from Theorem 4.1.

If Assumption 6 holds, the bound follows from Corollary 4.1 using the same argument.

When, in particular, we require Assumption 5 instead of Assumption 4, bounds in Corollary 4.2 take the following form: Corollary 4.3. Suppose that Assumptions 1, 2 and Assumption 5 hold, then for all s ✷ ❙

•❱ ✄ ✭s✮ ❯ ◆ ✭s✮• ✺ ✷▼ ✚ ◆ ✶ ✚ ❀
and therefore,

••❱ ✄ ❯ ◆ •• ✶ ✺ ✷▼ ✚ ◆ ✶ ✚ ✿
If in addition Assumption 6 holds,

••❱ ✄ ❯ ◆ •• ✶ ✺ ▼✚ ◆ ✶ ✚ ✿

Approximate Rolling Horizon Procedure

Suppose now that the players do not have exact information about the problem to be solved at RH1 in the RH procedure, but suppose they know or are able to compute an approximation of that value. We are interested in implementing a procedure where this last approximation is used instead of the value function of the game with finite horizon. We want to estimate the error introduced.

In the first scheme we study, the source of approximation lies in the determination of the finite-stage equilibrium ❱ ✄ ◆ ✶ . Specifically, ARH1 Choose some function ❱ close in some sense to ❱ ✄ ◆ ✶ , where ❱ ✄ ◆ ✶ is the ◆ ✶-stage value function.

ARH2 At iteration t, and for the current state s t , solve ARH4 Observe the achieved state at time t ✰ ✶: s t✰✶ .

ARH5 Set t ✿❂ t ✰ ✶ and go to step 2.

We will note with ⑦ ❯ ◆ the total discounted reward of the pair of stationary policies ⑦ ❢ ◆ and ⑦ ❣ ◆ .

The next result gives answers to questions Q1 and Q2 stated in this section for the sequence of successive rewards ⑦ ❯ ◆ .

A priori, the space | is not equipped with a metric. This makes it difficult to give a precise meaning to "close in some sense to ❱ ✄ ◆ ✶ " in step ARH1, for functions in |. On the other hand, in the space ▼ ✖ ✭❙✮ the ✖-norm induces a metric under Assumption 4. Adopting this (stronger) assumption instead of Assumption 3, we can prove the following results. Inria Theorem 4.2. Suppose that Assumptions 1, 2 and 4 hold, and that, for some ◆

, ••❱ ✄ ◆ ❱ ✄ ◆ ✶ •• ✖ ✺ ✧ ✶ . Let ❱ ✷ ▼ ✖ ✭❙✮ be a function such that ••❱ ✄ ◆ ✶ ❱ •• ✖ ✺ ✧ ✷ , consider a pair of stationary strategies ✭❢❀ ❣✮ ✷ ✆ st❛t ✂ st❛t such that ❚ ❢❀❣ ❱ ❂ ❚ ❱ , and let ⑦ ❯ ◆ ❂ ❱ ❢❀❣ . Then, ••❱ ✄ ⑦ ❯ ◆ •• ✖ ✺ ✷✚✭✧ ✶ ✰ ✧ ✷ ✮ ✶ ✚ ✿ Proof.
Let us start with the triangular inequality

••❱ ✄ ⑦ ❯ ◆ •• ✖ ✺ ••❱ ✄ ❱ ✄ ◆ •• ✖ ✰ ••❱ ✄ ◆ ⑦ ❯ ◆ •• ✖ ✿
To bound the first term in the r.h.s. of this inequality, observe that, for any ♠ ✷ ◆,

••❱ ✄ ◆✰♠ ❱ ✄ ◆ •• ✖ ✺ ♠ ✶ ❳ ❦❂✵ ••❱ ✄ ◆✰❦✰✶ ❱ ✄ ◆✰❦ •• ✖ ❂ ♠ ✶ ❳ ❦❂✵ ••❚ ❦✰✶ ❱ ✄ ◆ ❚ ❦✰✶ ❱ ✄ ◆ ✶ •• ✖ ✺ ♠ ✶ ❳ ❦❂✵ ✚ ❦✰✶ ••❱ ✄ ◆ ❱ ✄ ◆ ✶ •• ✖ ❂ ✚ ✭✶ ✚ ♠ ✮ ✶ ✚ ••❱ ✄ ◆ ❱ ✄ ◆ ✶ •• ✖ ❀ and, taking limits when ♠ ✦ ✶, ••❱ ✄ ❱ ✄ ◆ •• ✖ ✺ ✚ ✧ ✶ ✶ ✚ ❀ (23) using the bound ••❱ ✄ ◆ ❱ ✄ ◆ ✶ •• ✖ ✺ ✧ ✶ in the hypothesis.
To bound the second term, we use the facts that ❚ ❢❀❣ ❱ ❂ ❚ ❱ , ❚ ❢❀❣ ⑦ ❯ ◆ ❂ ⑦ ❯ ◆ , and that ❚ and ❚ ❢❀❣ are contractions of modulus ✚ (Lemma 3.1). With that,

••❱ ✄ ◆ ⑦ ❯ ◆ •• ✖ ❂ ••❱ ✄ ◆ ❚ ❢❀❣ ⑦ ❯ ◆ •• ✖ ✺ ••❱ ✄ ◆ ❚ ❢❀❣ ❱ •• ✖ ✰ ••❚ ❢❀❣ ❱ ❚ ❢❀❣ ⑦ ❯ ◆ •• ✖ ✺ ••❚❱ ✄ ◆ ✶ ❚ ❱ •• ✖ ✰ ✚••❱ ⑦ ❯ ◆ •• ✚ ✺ ✚✧ ✷ ✰ ✚ ✭••❱ ❱ ✄ ◆ ✶ •• ✖ ✰ ••❱ ✄ ◆ ✶ ❱ ✄ ◆ •• ✖ ✰ ••❱ ✄ ◆ ⑦ ❯ ◆ •• ✖ ✮ ✺ ✚✧ ✷ ✰ ✚✭✧ ✷ ✰ ✧ ✶ ✮ ✰ ✚ ••❱ ✄ ◆ ⑦ ❯ ◆ •• ✶ ❀ which implies ✭✶ ✚✮ ••❱ ✄ ◆ ⑦ ❯ ◆ •• ✖ ✺ ✷✚✧ ✷ ✰ ✚✧ ✶ ❀ or ••❱ ✄ ◆ ⑦ ❯ ◆ •• ✖ ✺ ✷✚✧ ✷ ✰ ✚✧ ✶ ✶ ✚ ✿ (24)
Finally, by ( 23) and (24),

••❱ ✄ ⑦ ❯ ◆ •• ✖ ✺ ✷✚✭✧ ✶ ✰ ✧ ✷ ✮ ✶ ✚ ✿ Corollary
◆ ❂ ✶, ••❱ ✄ ◆ ✶ ❱ •• ✖ ✺ ✧, consider a pair of policies ✭ ⑦ ❢ ◆ ❀ ⑦ ❣ ◆ ✮ ✷ ✆ st❛t ✂ st❛t such that ❚ ⑦ ❢ ◆ ❀⑦ ❣ ◆ ❱ ❂ ❚ ❱ , and let ⑦ ❯ ◆ ❂ ❱ ⑦ ❢ ◆ ❀⑦ ❣ ◆ . Then, ••❱ ✄ ⑦ ❯ ◆ •• ✖ ✺ ✷♠✚ ◆ ✶ ✚ ✰ ✷✚✧ ✶ ✚ ✿ If in addition Assumption 5 holds, ••❱ ✄ ⑦ ❯ ◆ •• ✶ ✺ ✷▼✚ ◆ ✶ ✚ ✰ ✷✚✧ ✶ ✚ ✿ Proof.
The proof follows by application of Theorem 4.2, with ✧ ✷ ✿❂ ✧, and considering that, as a consequence of Inequality (20),

••❱ ✄ ◆ ❱ ✄ ◆ ✶ •• ✖ ✺ ♠✚ ◆ ✶ ✶ ✚ ❂✿ ✧ ✶ ✿
◆, ••❱ ✄ ◆ ❱ ✄ ◆ ✶ •• ✖ ✺ ✧ ✶ . Let ❱ ✷ ▼ ✖ ✭❙✮ be a function such that ••❱ ✄ ◆ ✶ ❱ •• ✖ ✺ ✧ ✷
, and consider a policy ⑦ ❢ ◆ ✷ ✆ st❛t such that ❚ ⑦ ❢ ◆ ❱ ❂ ❚ ❱ . Then,

••❱ ✄ ⑦ ❯ ◆ •• ✖ ✺ ✷✚✭✧ ✶ ✰ ✧ ✷ ✮ ✶ ✚ ✿
where ⑦ ❯ ◆ ❂ ❱ ⑦ ❢ ◆ ❀❣ ✄ is the value of the pair ✭ ⑦ ❢ ◆ ❀ ❣ ✄ ✮, and ❣ ✄ ✷ st❛t is an infinite-horizon equilibrium strategy for player 2. 3 generalize to SMG our results for SMDP presented in [START_REF] Vecchia | Rolling Horizon Procedure on Controlled Semi-Markov Models. The Discounted Case[END_REF] and improve results for finite state discrete-time MG described in [START_REF] Chang | Two-person zero-sum games: receding horizon approach[END_REF]Theorems 6,[START_REF] Hernández-Lerma | Discrete-Time Markov Control Processes[END_REF]. The use of finer bounds even allows us to improve their "❖✭✭✶ ✚✮ ✷ ✮" term into a "❖✭✭✶ ✚✮ ✶ ✮" one.

☎ 5 Concluding Remarks

Through this work we have dealt with semi-Markov games models with discounted payoff, under different assumptions on the reward function. We have generalized known properties of the equilibria of games for both the finite-horizon and the infinite horizon case.

In addition, we have studied the performance of the rolling horizon procedure and of approximate rolling horizon procedures. We have proved the convergence of the values related to the rolling horizon procedure to the optimal reward function. We obtain simple pointwise convergence if Assumption 3 is verified and pointwise geometrical convergence when Assumption 4 holds. As a particular case, we have obtained uniform geometrical convergence for the case of uniformly bounded rewards functions, i.e. under Assumption 5.

Finally we have discussed an approximate rolling horizon procedure, based on the possibility of the controller not having perfect prediction of the future needed to take the best immediate action, but approximations of it. Here we have completed the analysis studying the case when the maximizer deals with the worst-case scenario.

Remark 2 . 1 .

 21 In view of Equations (1) and (2), Assumption 1 (c)-(d) implies (c') For each s ✷ ❙, and ❜ ✷ ❇ s , r✭s❀ ✁❀ ❜✮ is upper semi-continuous on ❆ s . (d') For each s ✷ ❙, and ❛ ✷ ❆ s , r✭s❀ ❛❀ ✁✮ is lower semi-continuous on ❇ s .InriaIt also implies the measurability of these functions, as required in the definition of ❱ ✙❀✌ ♥ and ❱ ✙❀✌ . ☎ Assumption 2. ✚ ✿❂ s✉♣ ✭s❀❛❀❜✮✷❑ ☞✭s❀ ❛❀ ❜✮ ❁ ✶.

  Assumption 4 (b) can be written ▲✖ ✺ ✖ equivalently. If r verifies Assumption 5, then by setting ✖ ✑ ✶ and ♠ ❂ ▼ , Assumption 4 is satisfied.

Theorem 3 . 1 .✵

 31 Suppose that Assumptions 1, 2 and 3 hold. Then (a) For all ✙ ✷ ✆ and ✌ ✷ , ❱ ✙❀✌ ❀ ❱ ✄ and ❱ ✄ are in |. (b) The finite-stage games have values. We have ❱ ✄ ✵ ✑ ✵ and, for ♥ ❂ ✶, the function ❱ ✄ ♥ ✿❂ ❚ ❱ ✄ ♥ ✶ ✷ | is the value function for the ♥-stage horizon problem, and the Markovian pair of policies ❢❢ ✄ , where the functions ❢ ✄ ❦ and ❣ ✄ ❦ are the corresponding maxi-minimizing functions, for ❦ ❂ ✵❀ ✿✿✿❀ ♥ ✶, form an equilibrium.

Remark 4 . 1 .

 41 Theorem 4.1 generalizes to SMG the results in [5, Theorem 4.2] for discrete-time MDP. ☎ In order to improve the bounds obtained, we consider the following Positive Value Assumption Assumption 6. ❱ ✄ ✶ ❂ ✵.

Proposition 4 . 1 .

 41 Suppose that Assumption 6 holds. Then for ♥ ✷ ◆ and for all s ✷ ❙,❱ ✄ ♥ ✭s✮ ✺ ❱ ✄ ♥✰✶ ✭s✮.Proof. Since ❱ ✄ ✵ ✑ ✵, we can write Assumption 6 as ❱ ✄ ✵ ✭s✮ ✺ ❱ ✄ ✶ ✭s✮, for all s ✷ ❙. If this is the case, for any pair of strategies ✭❢❀ ❣✮ ✷ ✆ st❛t ✂ st❛t , there holds ❚ ❢❀❣ ❱ ✄ ✵ ✺ ❚ ❢❀❣ ❱ ✄ ✶ , and by Lemma A.1, ❚ ❱ ✄ ✵ ✺ ❚ ❱ ✄ ✶ . The last inequality rewrites as ❱ ✄ ✶ ✺ ❱ ✄ ✷ . The result follows now by induction with similar arguments.

Corollary 4 . 1 .

 41 If in Theorem 4.1 Assumption 6 holds, then,•❱ ✄ ❯ ◆ • ✺ ✚ ◆ ✂ ▲ ◆ |✿ Proof. If Assumption 6 holds, it is possible to improve the bound (21) into ❱ ✄ ◆ ✺ ❚ ❢ ◆ ❀❣ ◆ ❱ ✄ ◆ ,and by application of Lemma 4.1, we get ❱ ✄ ◆ ✺ ❯ ◆ . In other terms, Inequality (22) now reads

Remark 4 . 2 .Remark 4 . 3 .

 4243 Again, if Assumptions 1, 2 and 4 hold, with ❱ ✷ ▼ ✖ ✭❙✮ an in Theorem 4.3, and ⑦ ❢ ◆ ✷ ✆ st❛t such that ❚ ⑦ ❢ ◆ ❱ ❂ ❚ ❱ , in the worst case scenario, Theorems 4.2 and 4.

  1. Similarly, for player 2, a Markov strategy ✌ is stationary if there exists ❣ ✷ P✭❇•❙✮ such that ❣✭s✮ ✷ P✭❇ s ✮ and ❣ ♥ ❂ ❣ for all s ✷ ❙ and ♥ ✷ ◆. For player 2, we denote st❛t the set of all stationary strategies. For each pair of strategies ✭✙❀ ✌✮ ✷ ✆✂ , and any initial state s there exist a unique probability measure P ✙❀✌ s and stochastic processes ❢❙ t ❣, ❢❆ t ❣, ❢❇ t ❣ and ❢✍ t ❣. ❙ t , ❆ t and ❇ t represent the state and the actions at the t-th decision epoch. ❊ ✙❀✌ s denotes the expectation operator with

	respect to P ✙❀✌ s . We note	☞✭s❀ ❛❀ ❜✮ ✿❂	) ✶ ✵	❡ ☛t ❋ ✭dt•s❀ ❛❀ ❜✮	(1)
	the Laplace transform of ✍, conditioned on ✭s❀ ❛❀ ❜✮ and evaluated at ☛, and
		★✭s❀ ❛❀ ❜✮ ❂	✶ ☞✭s❀ ❛❀ ❜✮ ☛	✿

  linear subspace of ▼✭❙✮ of the functions with finite ✖-weighted norm. This is a Banach space.

	Define the operator ❚ ✿ ▼✭❙✮ ✼ ✦ ▼✭❙✮ by ✚	)	✛
	✭❚ ✈✮✭s✮ ✿❂ s✉♣ ❛✷❆s	✐♥❢ ❜✷❇s	r✭s❀ ❛❀ ❜✮ ✰ ☞✭s❀ ❛❀ ❜✮	❙	✈✭③✮◗✭d③•s❀ ❛❀ ❜✮	❀	(9)

and, given a pair of stationary policies ❢ ✷ ✆ st❛t and ❣ ✷ st❛t , ❚ ❢❀❣ ✿ ▼✭❙✮ ✼ ✦ ▼✭❙✮

✭❚ ❢❀❣ ✈✮✭s✮ ✿❂ r✭s❀ ❢❀ ❣✮ ✰ ☞✭s❀ ❢❀ ❣✮ ) ❙ ✈✭③✮◗✭d③•s❀ ❢❀ ❣✮ ✿

(10)

We first state general properties of these operators. Lemma 3.1. Under Assumptions 1, 2 and 3, the operator ❚ maps | to itself. Under Assumptions 1, 2 and 4, ❚ maps ▼ ✖ ✭❙✮ to itself. If ✈ is a bounded function, then ❚ ✈ is also bounded. The same three properties hold for the operators ❚ ❢❀❣ .

Proof. First, observe that ✚✭▲|✮✭s✮ ❂ P ✶ t❂✶ ✚ t ✭▲ t r ✵ ✮✭s✮ ❂ |✭s✮ r ✵ ✭s✮. Next, note that for all

  RH1 At iteration t, and for the current state s t , solve the ◆ -stage game (FHP), taking s t as initial state. A pair of actions ❢ ◆ ✭s t ✮, ❣ ◆ ✭s t ✮ is obtained. RH2 Apply ❛ t ❂ ❢ ◆ ✭s t ✮, ❜ t ❂ ❣ ◆ ✭s t ✮. RH3 Observe the achieved state at time t ✰ ✶: s t✰✶ . RH4 Set t ✿❂ t ✰ ✶ and go to step 1.

  4.4. Suppose that Assumptions 1, 2 and 4 hold. Let ❱ ✷ ▼ ✖ ✭❙✮ be a function such that for some

  The second statement follows as in Corollary 4.2.So far in this work we have considered the situation where, given an approximate value function ❱ , the maximizer plays the policy ⑦ ❢ ✷ ✆ st❛t such that ❚ ⑦ ❢❀⑦ ❣ ❱ ❂ ❚ ❱ . Suppose now that this player chooses any ⑦ ❢ ✷ ✆ st❛t such that ✭❚ ❢ ❱ ✮✭s✮ ❂ ✭❚ ❱ ✮✭s✮ ❀

	where	❜✷❇s ✭❚ ❢ ❱ ✮✭s✮ ✿❂ ✐♥❢	r✭s❀ ❢❀ ❜✮ ✰ ☞✭s❀ ❢❀ ❜✮ ✚	)	❙	❱ ✭③✮◗✭d③•s❀ ❢❀ ❜✮ ✛

✿

This situation corresponds to the worst-case scenario for player 1. The next result gives us bounds for this second ARH framework. In this worst-case approach we keep the notation ⑦ ❯ ◆ to denote the value function when the corresponding strategies are used.

The proof of the next result is ommited, due to its similarity with the one of Theorem 4.2.

Theorem 4.3. Suppose that Assumptions 1, 2 and 4 hold, and that, for some

  Proof. Without losing generality, let us suppose✐♥❢ ②✷( s✉♣ ①✷❳ ❢ ✭①❀ ②✮ ✐♥❢ ②✷( s✉♣ ①✷❳ ❣✭①❀ ②✮ ❂ ✵. If it is not the case, interchange ❢ with ❣. Given ✧ ❃ ✵, take ② ✄ ✷ ( such that ✭①❀ ② ✄ ✮ ✺ ❢ ✭① ✄ ❀ ② ✄ ✮ ✰ ✧❀ ①✷❳ ❣✭①❀ ② ✄ ✮ ✰ ✧ ✺ ❢ ✭① ✄ ❀ ② ✄ ✮ ❣✭① ✄ ❀ ② ✄ ✮ ✰ ✷✧ ❀Since ✧ is any arbitrary positive number, the first inequality is proved.The second inequality follows in the same manner, taking, for✧ ❃ ✵, ① ✄ ✷ ❳ such that Indeed, if s✉♣ ①✷❳ ✐♥❢ ②✷( ❢ ✭①❀ ②✮ s✉♣ ①✷❳ ✐♥❢ ②✷( ❣✭①❀ ②✮ ❂ ✵, ②✷( ❢ ✭① ✄ ❀ ②✮ ✐♥❢ ②✷( ❣✭① ✄ ❀ ②✮ ✺ ❢ ✭① ✄ ❀ ② ✄ ✮ ❣✭① ✄ ❀ ② ✄ ✮ ✰ ✷✧ ❀

			s✉♣ ①✷❳	❢ ✭①❀ ② ✄ ✮ s✉♣
	which implies
		☞ ☞ ☞ ☞ ✐♥❢ ②✷( s✉♣ ①✷❳	❢ ✭①❀ ②✮	✐♥❢ ②✷( s✉♣ ①✷❳	❣✭①❀ ②✮ ☞ ☞ ☞ ☞ ✺ s✉♣ ①✷❳	s✉♣ ②✷(	•❢✭①❀ ②✮ ❣✭①❀ ②✮• ✰ ✷✧ ✿
								s✉♣ ①✷❳	✐♥❢ ②✷( ❢ ✭①❀ ②✮ ✺ ✐♥❢ ②✷( ❢ ✭① ✄ ❀ ②✮ ✰ ✧
	and ② ✄ ✷ ( such that			❣✭① ✄ ❀ ② ✄ ✮ ✧ ✺ ✐♥❢ ②✷( ❣✭① ✄ ❀ ②✮ ✿
		s✉♣ ①✷❳	✐♥❢ ②✷( ❢ ✭①❀ ②✮ s✉♣ ①✷❳	✐♥❢ ②✷( ❣✭①❀ ②✮ ✺ ✐♥❢
	and	☞ ☞ ☞ ☞ s✉♣ ①✷❳	✐♥❢ ②✷( ❢ ✭①❀ ②✮ s✉♣ ①✷❳	✐♥❢ ②✷( ❣✭①❀ ②✮	☞ ☞ ☞ ☞ ✺ s✉♣ ①✷❳	s✉♣ ②✷(	•❢✭①❀ ②✮ ❣✭①❀ ②✮• ✰ ✷✧ ✿
						☞ ☞ ☞ ☞ ✐♥❢ ②✷( s✉♣ ①✷❳	❢ ✭①❀ ②✮	✐♥❢ ②✷( s✉♣ ①✷❳	❣✭①❀ ②✮	☞ ☞ ☞ ☞ ✺ s✉♣ ①✷❳	s✉♣ ②✷(	•❢✭①❀ ②✮ ❣✭①❀ ②✮•
	and					☞ ☞ ☞ ☞ s✉♣ ①✷❳	✐♥❢ ②✷( ❢ ✭①❀ ②✮ s✉♣ ①✷❳	✐♥❢ ②✷( ❣✭①❀ ②✮ ☞ ☞ ☞ ☞ ✺ s✉♣ ①✷❳	s✉♣ ②✷(	•❢✭①❀ ②✮ ❣✭①❀ ②✮• ✿
								s✉♣ ①✷❳	❣✭①❀ ② ✄ ✮ ✧ ✺ ✐♥❢ ②✷( s✉♣ ①✷❳	❣✭①❀ ②✮ ✿
	Then				✐♥❢ ②✷( s✉♣ ①✷❳	❢ ✭①❀ ②✮	✐♥❢ ②✷( s✉♣ ①✷❳	❣✭①❀ ②✮ ✺ s✉♣ ①✷❳	❢ ✭①❀ ② ✄ ✮ s✉♣ ①✷❳	❣✭①❀ ② ✄ ✮ ✰ ✧ ✿
	Now, taking ① ✄ ✷ ❳ such that
								s✉♣ ①✷❳
								Inria

❢ RR n°8019 RESEARCH CENTRE SOPHIA ANTIPOLIS -MÉDITERRANÉE 2004 route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr

RR n°8019

For continuous-time models, it is important to distinguish a time horizon and an horizon measured in a number of control/game stages.RR n°8019