Olivier Buffet
email: olivier.buffet@loria.fr

Jilles Dibangoye
email: jilles-steeve.dibangoye@insa-lyon.fr

Abdallah Saffidine
email: abdallahs@cse.unsw.edu.au

Vincent Thomas
email: vincent.thomas@loria.fr

Heuristic Search Value Iteration for zero-sum Stochastic Games

In sequential decision-making, heuristic search algorithms allow exploiting both the initial situation and an admissible heuristic to efficiently search for an optimal solution, often for planning purposes. Such algorithms exist for problems with uncertain dynamics, partial observability, multiple criteria, or multiple collaborating agents. Here we look at two-player zero-sum stochastic games with discounted criterion, in a view to propose a solution tailored to the fully observable case, while solutions have been proposed for particular, though still more general, partially observable cases. This setting induces reasoning on both a lower and an upper bound of the value function, which leads us to proposing zsSG-HSVI, an algorithm based on Heuristic Search Value Iteration (HSVI), and which thus relies on generating trajectories. We demonstrate that, each player acting optimistically, and employing simple heuristic initializations, HSVI's convergence in finite time to an -optimal solution is preserved. An empirical study of the resulting approach is conducted on benchmark problems of various sizes.

I. INTRODUCTION

H EURISTIC search techniques have been introduced to solve single-agent single-criterion optimization problems in deterministic settings, often for planning purposes, with algorithms like A*, (L)RTA*, or RBFS [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF][START_REF] Bulitko | Learning in real-time search: A unifying framework[END_REF]. They have then been extended to solving problems with stochastic dynamics in the MDP or POMDP framework as in (L)RTDP, (L)AO*, or HSVI [START_REF] Bonet | Labeled RTDP: Improving the convergence of real-time dynamic programming[END_REF][START_REF] Hansen | LAO*: A heuristic search algorithm that finds solutions with loops[END_REF][START_REF] Smith | Point-based POMDP algorithms: Improved analysis and implementation[END_REF], and even in multi-agent collaborative settings in MAA* or FB-HSVI [START_REF] Szer | MAA*: A heuristic search algorithm for solving decentralized POMDPs[END_REF][START_REF] Dibangoye | Optimally solving Dec-POMDPs as continuousstate MDPs[END_REF]. In all these cases, a single criterion is considered, so that guiding the exploration by being optimistic remains a rather straightforward thing to do, even when planning for multiple agents. When multiple criteria are considered (for a single agent or collaborative agents), this guidance can be adapted both when aggregating the criteria or when searching for a Pareto front [START_REF] Roijers | A survey of multi-objective sequential decisionmaking[END_REF]. Our focus here is on non-collaborative multi-agent problems. We look in particular at discounted two-player zero-sum stochastic games (zs-SGs) with perfect information and finite state and action sets. Such games can serve for instance in robust control [START_REF] Altman | Flow control using the theory of zero-sum Markov games[END_REF], or in solving or analyzing Real-Time Strategy games (e.g., µRTS [START_REF] Ontañón | The first MicroRTS artificial intelligence competition[END_REF]). While particular partially observable SGs, hence more general problems, have been solved through heuristic search [START_REF] Horák | Heuristic search value iteration for one-sided partially observable stochastic games[END_REF][START_REF] Horák | Solving partially observable stochastic games with public observations[END_REF] (see next section), this work fills a gap by proposing and studying a simpler solution that is better suited to the fully observable case.

Here, discounted zs-SGs are equipped with (i) an initial state s 0 , and (ii) initial upper and lower bounds (U and L) of the optimal value function, i.e., admissible heuristics. Under these assumptions, we look at learning/trajectory-generating algorithmic schemes (à la LRTA*, (L)RTDP or HSVI), and show that trajectories can be generated by letting the two players act optimistically-one greedily w.r.t. to an upperbound U of the optimal (Nash equilibrium) value, the other w.r.t. to a lower-bound L-while ensuring that these two bounds converge to the optimum. Using two bounds naturally leads to algorithms resembling Bounded-RTDP and HSVI [START_REF] Mcmahan | Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees[END_REF][START_REF] Smith | Point-based POMDP algorithms: Improved analysis and implementation[END_REF]. We take inspiration from HSVI, to derive our main contribution, zsSG-HSVI, a heuristic-search algorithm that provably converges in finite time to an error-bounded solution.

The paper is organized as follows. It first discusses related work on stochastic games in Section II and provides background on normal-form games, Markov decision processes (MDPs), and stochastic games in Section III. Shapley's reference algorithm, whose stopping criterion relies on the Bellman residual (BR), is called here Shapley-BR. It is presented alongside a variant we propose, Shapley-Gap, which updates both a lower and an upper bound of the optimal value function, stopping when the gap between them is small enough. This new algorithm combines properties of Shapley-BR and our contributed zsSG-HSVI. Then, Section IV presents preliminary results on upper-and lower-bounded normalform games before proposing the key ingredients to deriving zsSG-HSVI and proving its convergence. Finally, Section V presents an empirical study before concluding in Section VI. Complementary discussions and benchmark problem descriptions are provided as supplementary material (referred here as appendices).

II. RELATED WORK

Discounted zero-sum stochastic games (zs-SGs) have been addressed using approaches such as exact dynamic programming (DP) [START_REF] Raghavan | Algorithms for stochastic games -a survey[END_REF] (akin to Value or Policy Iteration for MDPs), reinforcement learning (RL) [START_REF] Littman | A generalized reinforcement learning model: Convergence and applications[END_REF], policy gradient [START_REF] Bowling | Multiagent learning using a variable learning rate[END_REF], and approximate DP [START_REF] Lagoudakis | Value function approximation inf zero-sum Markov games[END_REF][START_REF] Pérolat | Softened approximate policy iteration for Markov games[END_REF].

The total reward criterion common in board games, i.e., nondiscounted zs-SGs, requires all trajectories to end in a terminal state, and has been addressed with (i) RL [START_REF] Littman | A generalized reinforcement learning model: Convergence and applications[END_REF], (ii) backward induction [START_REF] Saffidine | Alpha-Beta pruning for games with simultaneous moves[END_REF][START_REF] Bošanský | Algorithms for computing strategies in two-player simultaneous move games[END_REF], i.e., applying DP on reachable states while pruning irrelevant branches based on conservative estimates, (iii) sub-optimal heuristic search algorithms [START_REF] Churchill | Fast heuristic search for RTS game combat scenarios[END_REF][START_REF] Moraes | Nested-greedy search for adversarial real-time games[END_REF], when real-time constraints have to be enforced, and (iv) Simultaneous Move MCTS [START_REF] Bošanský | Algorithms for computing strategies in two-player simultaneous move games[END_REF]. 1 Here, exact DP algorithms come with the strongest convergence guarantees. Among them, backward induction is a form of optimal heuristic search. The present work differs in that it addresses problems with cycles, nonzero rewards not restricted to terminal states (which may not exist), and a discounted criterion.

Recent works addressed particular cases of discounted (twoplayer) zero-sum partially observable stochastic games (zs-POSGs) using heuristic search: Horák et al. [START_REF] Horák | Heuristic search value iteration for one-sided partially observable stochastic games[END_REF] considered One-Sided POSGs, i.e., the case where one player has access to the system state, plus the action and observation of the other player, and Horák and Bošanský [START_REF] Horák | Solving partially observable stochastic games with public observations[END_REF] considered POSGs with public observations, i.e., the case where each Player i knows his own private state s i and both players receive the same public observations of each player's private state, so that they have common knowledge of Player -i's belief over Player i's private state. Moving from MDPs and POMDPs (as in Smith's work 2007) to these settings requires changes to the algorithm that make a different approach necessary to theoretically analyze the finite-time convergence. In contrast, the present paper looks at the simpler case of (fully observable) stochastic games, which allows for an algorithm closer to the original HSVI, as well as similar finite-time convergence results, thus suggesting different convergence behaviors compared to the aforementioned POSG versions.

To sum up, the present work thus fills a gap, both from a theoretical and empirical viewpoint, in the study of heuristic search for zero-sum games in between (fully observable) sequential games, non-discounted zs-SGs, and some discounted zs-POSGs. We now turn to presenting necessary background on game theory and heuristic search.

III. BACKGROUND

In the following, upperscripts indicate players, and subscripts indicate time steps or iterations.

A. Normal-form/Matrix Games

A two-player game in normal-form is defined by a tuple

Γ def = A 1 , A 2 , v 1 , v 2
, where A i is player i's (i ∈ {1, 2}) finite set of pure strategies, and v i : A 1 × A2 → R is player i's payoff function. The objective is then, for each player, to maximize his expected payoff. Unless they have identical payoff functions, this is not about finding an optimum of some function, but an equilibrium. A classical solution concept is that of Nash Equilibrium (NE) [START_REF] Nash | Equilibrium points in n-person games[END_REF], defined as a pair (d 1 , d 2 ) ∈ ∆(A 1 ) × ∆(A 2 ) of mixed strategies, i.e., 1 For other criteria, refer to [START_REF]Stochastic games[END_REF].

probability distributions over pure strategies, such that no player has any incentive to deviate on his own:

∀d 1 ∈ ∆(A 1 ), v 1 (d 1 , d 2 ) ≤ v 1 (d 1 , d 2 ), ∀d 2 ∈ ∆(A 2 ), v 2 (d 1 , d 2 ) ≤ v 2 (d 1 , d 2 ).
In a zero-sum game, v 1 + v 2 = 0-i.e., one player's gain is the other player's loss-, and we will typically note v = v 1 = -v 2 . Player 1 then maximizes his expected payoff, while Player 2 minimizes it. Also, as demonstrated by von Neumann [START_REF] Neumann | Zur Theorie der Gesellschaftsspiele[END_REF], such a game Γ has a single Nash equilibrium value NEV(Γ) equal to both the minimax and maximin values. As a consequence, strategies forming a (joint) Nash equilibrium strategy (NES) can be found by solving (often as Linear Programs):

d NES,1 = arg max d 1 ∈∆(A 1 ) min a 2 ∈A 2 v(d 1 , a 2 ), d NES,2 = arg min d 2 ∈∆(A 2 ) max a 1 ∈A 1 v(a 1 , d 2 ).

B. Stochastic Games

A discounted 2-player zero-sum stochastic (or Markov) game (zs-SG) [START_REF] Shapley | Stochastic games[END_REF][START_REF]Some topics in two person games[END_REF][START_REF] Raghavan | Algorithms for stochastic games -a survey[END_REF] is specified by a tuple S, A 1 , A 2 , P, r, γ, s 0 , where S is a finite set of states, A 1 and A 2 are finite sets of actions (one per player), P a 1 ,a 2 (s |s) is the probability to transition from state s to s when actions a 1 and a 2 are performed; r(s, a 1 , a 2 ) is a (scalar) reward function; γ ∈ [0, 1) is a discount factor; and s 0 is the initial state. Player 1's objective is to maximize the expected γ-discounted sum of rewards E[ t γ t R t |s 0 ] while Player 2's objective is to minimize that same quantity. For convenience, we will denote: π i : S → ∆(A i ) a stochastic strategy for player i; and π = (π 1 , π 2 ) a joint strategy (or pair of strategies) for both players.

Such a game can be re-written in normal form and solved by searching for a NE (as a mixed strategy). Yet, a more satisfying solution concept here is that of Markov perfect equilibrium (MPE), i.e., noting that a local normal-form game is faced in each state, solutions which consist in one NE per reachable state, with Markov strategies, i.e., decisions depending on the current state alone, not on past information. 2 Let us thus define (i), for any s ∈ S and V ∈ R |S| , the Shapley matrix game

Γ s (V ) def = [r(s, •, •) + γ s P •,• (s |s)V (s )] (where (•, •)
denotes the various action pairs (a 1 , a 2 ) in the matrix), i.e., the normal-form game faced when in state s and assuming that the expected discounted return obtained from subsequent states is specified by value function V , and (ii) Shapley's optimality operator H : V → NEV(Γ • (V )), which computes the NEV of each state's Shapley matrix game given V . H is a contraction mapping, and its unique fixed point is the value function common to all MPE strategies, denoted V * . This implies that, in any state s, all MPE strategies induce the same expected discounted returned. Shapley's algorithm for solving zs-SGs Shapley [START_REF] Shapley | Stochastic games[END_REF], analogous to value iteration (VI) for MDPs, consists in iteratively applying this operator to generate a sequence of value functions V k (randomly initialized) until -convergence (details below), as depicted in Appendix A (Algorithm 3). Then, when in some state s at execution time, both players have to act according to a NES of the induced Shapley game matrix in s. Note: other exact algorithms also handle problems with no initial states [START_REF] Raghavan | Algorithms for stochastic games -a survey[END_REF], while the present contribution exploits one.

Stopping Criteria for Shapley's Algorithm: We first generalize Shapley's algorithm for 2-player zero-sum stochastic games by distinguishing whether moves are simultaneous or sequential, player 1 acting first or second. This simply means trading the (simultaneous) minmax operator for Nash equilibria in simultaneous normal-form games for a min-thenmax or max-then-min operator. In all three cases the same algorithm converges due to the contraction property induced by the discount factor.

Whatever the operator at hand, the algorithm usually (i) updates the values asynchronously (à la Gauss-Seidel) and (ii) is stopped when the Bellman residual (BR) is below some threshold θ, i.e. V k -V k-1 ∞ ≤ θ. Then, as for VI in the MDP setting, to ensure that the value of the resulting pair of strategies π k is within > 0 of the optimum, this algorithm (denoted ShapleyBR) should use θ = 1 2 1-γ γ . All three update operators are monotone, i.e., (i

) if V k ≥ V * (∀s), then V k+1 ≥ V * , and (ii) if V k ≤ V * (∀s), then V k+1 ≤ V * .
This allows us to propose a bounded algorithm, ShapleyGap, that maintains an upper-and a lower-bound (U and L) of V * , performing updates only at states s where the gap/width U (s) -L(s) is larger than the desired threshold > 0, and stopping the algorithm when U -L ∞ < . The max (resp. min) player should then act "optimally" with respect to L (resp. U ). The whole process behind ShapleyGap is detailed in Appendix A (Algorithm 4), and its finite-time convergence is stated further on in Corollary 2.

C. MDPs and HSVI

Markov decision processes (MDPs) [START_REF] Bellman | The theory of dynamic programming[END_REF][START_REF] Bertsekas | Neurodynamic Programming[END_REF] can be seen as stochastic games in which one player-without loss of generality, (minimizing) Player 2-has a single available action, thus no decision to make. The problem is then to find a strategy, also referred to as a policy, for (maximizing) Player 1. Here, the NEV becomes the optimal value function V * , and acting greedily with respect to the value function induces an optimal policy, so that there always exists a deterministic optimal policy.

Bounded RTDP [START_REF] Mcmahan | Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees[END_REF] and HSVI [START_REF] Smith | Point-based POMDP algorithms: Improved analysis and implementation[END_REF] (detailed in Algorithm 1) are two algorithms that solve MDPs relying on (i) an initial state s 0 to focus on most relevant parts of the state space, (ii) upper and lower bounds (U and L) of the optimal value function V * , and (iii) performing pointwise updates of these bounds at the states encountered while following trajectories. While HSVI was initially introduced for solving POMDPs, we focus on the generic (MDP) version presented by Smith [START_REF] Smith | Probabilistic planning for robotic exploration[END_REF] rather than BRTDP, because it comes with stronger theoretical guarantees (e.g., it converges in finite time rather than in the limit). Both HSVI and BRTDP select actions greedily w.r.t. the upper bound, and stop sampling trajectories when U (s 0 )-L(s 0 ) is below a threshold > 0. To select the next state given s and a, HSVI picks a state s maximizing excess(s , δ) = P a (s |s)(U (s ) -L(s ) -γ -δ ), where δ is the depth of s in the current trajectory, to focus on states whose updates are more likely to help. 3 As we shall see later, the term γ -δ ensures the convergence through a recursive process.

IV. ALGORITHM AND CONVERGENCE PROOF

A. Bounding a Normal-form Game

As explained in the introduction, we would like to propose heuristic search algorithms (à la HSVI) for solving 2-player zs-SGs, i.e., focusing the computational efforts on relevant parts of the state space by exploiting (i) the knowledge of the initial state s 0 , and (ii) admissible heuristics for both players, used to initialize upper and lower bounds of the value function. While classical (1-player vs. nature) heuristic search requires only an upper bound of the value function to optimistically guide the search, 2-player zs-SGs shall require both an upper and a lower bound (so as (i) to be optimistic for both players, and (ii) to derive each player's executed strategy). We will thus end up computing Nash Equilibria (NEs) for both upper-and lower-bounding Shapley matrix games Γ s (U ) and Γ s (L) in each encountered state s. Then, what does happen if, in some state s, both NEs are equal? As demonstrated by the next two results, in this case the obtained value is the NE value for that state.

Lemma 1. If zs normal-form game Γ up 's payoff v up upper- bounds same-dimension zs normal-form game Γ lo 's payoff v lo , then NEV(Γ up ) ≥ NEV(Γ lo ). Proof. ∀a 1 , a 2 v up (a 1 , a 2 ) ≥ v lo (a 1 , a 2 )
3 BRTDP samples a state according to a distribution which resembles a normalized version of this excess function.

∀a 1 min a 2 v up (a 1 , a 2 ) ≥ min a 2 v lo (a 1 , a 2 ) max d 1 min a 2 a 1 d 1 (a 1 )v up (a 1 , a 2 ) ≥ max d 1 min a 2 a 1 d 1 (a 1 )v lo (a 1 , a 2 ) i.e., NEV(Γ up ) ≥ NEV(Γ lo ).
Corollary 1. In a zs-SG, if, in some state s, the NE values of Γ s (L) and Γ s (U ) are equal, then

NEV(Γ s (L)) = NEV(Γ s (U ))
is the NE value, V * (s), of the converged zs Shapley game in that state (for the MPE of the zs-SG).

Proof. Applying the previous lemma in some state s, we always have in our setting:

NEV(Γ s (L)) ≤ V * (s) ≤ NEV(Γ s (U )). So, when NEV(Γ s (L)) = NEV(Γ s (U ))
, this is also the value of V * (s).

We now turn to showing how to adapt HSVI to the zs-SG setting. While U (s 0 ) -L(s 0 ) > , HSVI generates trajectories by applying, in each encountered state, (i) an action selection strategy and (ii) a next-state selection strategy. We now present these strategies and other details of the proposed algorithm, and prove that the latter finds strategies which are -optimal in s 0 in finite time.

B. Joint Action Selection

In an MDP, greedy action selection w.r.t. an optimistic bound guarantees convergence. In a zs-SG, assuming that player 2 has only one action, player 1 faces a rewardbased MDP and its optimistic bound is the upper one (U ). Conversely, if player 1 has only one action, player 2 faces a cost-based MDP and its optimistic bound is the lower one (L).

Hence, noting NES i (Γ) a NE strategy for player i in game Γ, the proposed exploration strategy, when in state s:

• player 1 picks stochastic action d U,1 greedily w.r.t. to the upper bound U , i.e., playing NES 1 (Γ s (U )); and • player 2 picks stochastic action d L,2 greedily w.r.t. to the lower bound L, i.e., playing NES 2 (Γ s (L)). We call the resulting joint decision rule d = (d U,1 , d L,2 ) a tentative NES at s.

C. Next State Selection

After picking a joint strategy, the next state s can be selected in various ways-e.g., sampling

a 1 from d 1 (•), a 2 from d 2 (•), then s from P a 1 ,a 2 (•|s) (à la (L)RTDP
). Yet, to preserve HSVI's convergence guarantees, we prefer selecting a next state s maximizing the expected excess EE(s,

d 1 , d 2 , s , δ) def = a 1 ,a 2 d 1 (a 1 )d 2 (a 2 )P a 1 ,a 2 (s |s) width( V (s )) -γ -δ excess(s ,δ)
, where V denotes the pair (L, U ), width((x, y)) def = y -x, and δ is the current depth. Note: In the following, operators on value functions such as H are naturally extended to pairs of function, e.g., H( V ) = (H(L), H(U )).

D. Value Update

As for classical HSVI, we use point-based operators to update the lower and upper bounds, i.e., operators that are applied at a given point s, and define:

• a uniformly improvable (UI) lower bound L as respecting HL ≥ L; and • a strong point-based update operator for the lower bound K L • as respecting, for each s where it is applied and any L, (i) (K L s L)(s) = (HL)(s) and (ii) (K L s L)(s ) ≤ (HL)(s ) in any other point s (the same definitions apply to the upper bound U by reverting inequality operators). Uniform improvability, along with monotonicity (Sec. III-B), is necessary to ensure that lower (resp. upper) bounds remain lower (resp. upper) bounds. The strong property is required to ensure convergence to the optimal value function in the limit.

In our setting, we use a single update operator K s for both bounds, which, for any state s, only updates the value for this state with the natural value updates:

(K s L)(s) def = NEV(Γ s (L)), (K s U )(s) def = NEV(Γ s (U )),
and leaves L and U unchanged for other states.

As in the MDP setting, we have (for both L and U ) that: (i) our proposed operator is strong, thus conservative [START_REF] Smith | Probabilistic planning for robotic exploration[END_REF]Def. 3.24,3.25]; and (ii) any conservative update operator preserves UI [START_REF] Smith | Probabilistic planning for robotic exploration[END_REF]Th. 3.29]. We thus mainly need to ensure that our initializations induce UI bounds (see next sub-section).

E. Upper-and Lower-Bound Initializations

As for POMDPs, one way to initialize the lower and upper bounds is to compute the fixed point of an operator that loweror upper-bounds Shapley's optimality operator H. Table I shows the candidate operators for both bounds: G [L/U ] SEQ : a sequential game approximation-also known as serialization-, i.e., setting U as the optimal value if player 1 acts after player 2 (the latter knowing the action choice of the former), and L as the opposite; G

[L/U ]

TRIV : trivial approximations that translate to, ∀s,

U (s) = 1 1 -γ R max def = 1 1 -γ max s ,a 1 ,a 2 r(s , a 1 , a 2 ) and L(s) = 1 1 -γ R min def = 1 1 -γ min s ,a 1 ,a 2 r(s , a 1 , a 2 ).
The former approximations require solving sequential games, possibly with Shapley-or HSVI-like algorithms. 4 The latter two values can be computed in constant time.

Uniform Improvability: Without loss of generality, let us discuss Uniform Improvability only for upper bounds. As proposed above, the initial upper bound U is obtained as the unique fixed point of some update operator K up which always "upper-bounds" Shapley's optimality operator H. As a consequence, HU ≤ K up U = U , so that U is uniformly improvable. This approach is similar to Theorem 3.20 in [24, page 71], and also applies to lower bounds.

(G U TRIV V )(s) = max s ,a 1 ,a 2 ,s r(s , a 1 , a 2 ) + γV (s ) (G U SEQ V )(s) = min a 2 max a 1 Γ s (V )(a 1 , a 2 ) (HV )(s) = min d 2 max a 1 Γ s (V )(a 1 , d 2 ) = NEV(Γ s (V )) = max d 1 min a 2 Γ s (V )(d 1 , a 2 ) (G L SEQ V )(s) = max a 1 min a 2 Γ s (V )(a 1 , a 2 ) (G L TRIV V )(s) = min s ,a 1 ,a 2 ,s r(s , a 1 , a 2 ) + γV (s )
On-demand Initializations: The following discussion on how to handle initializations is set in the context of zs-SGs, but applies to other settings as well.

Value function initializations are often considered as part of pre-computations performed a priori for all states, either because all states equally need initializations (as here in Shap-leyBR and ShapleyGap, but contrary to HSVI), or because the initialization process provides values for all states anyway (as here with the trivial initializations). Initializations based on serialized versions of (simultaneous move) zs-SGs can be obtained either through a serialized version of ShapleyBR or ShapleyGap (i.e., with "serialized" operators), or through a serialized version of HSVI. For (simultaneous) HSVI, our algorithm will thus try to benefit from on-demand initializations, calling (serialized) HSVI whenever needed. Note that a priori initializations shall typically used with "uniform" stopping criteria, i.e., requesting the same property to be satisfied on all states, while on demand initializations shall satisfy a property at least at the state at hand, and possibly depending on the current depth for algorithms such as HSVI (because less precision is needed when going deeper in a trajectory). Some implementation details are provided in Section V. Note that, for the sake of clarity, Algorithm 2 does not reflect the process of on-demand initializations.

F. Trials Termination Criterion and Convergence Proof

Let us end a trial when reaching a state s at depth δ that is NEV-finished-i.e., when the excess, excess(s, δ), is non-positive. Using this trial termination condition is the last element needed to ensure that the zs-SG version of HSVI converges in finite time. We essentially need to prove the following key lemma before using results from [START_REF] Smith | Probabilistic planning for robotic exploration[END_REF].

Lemma 2 (Cf. [24, Lemma 6.1]). Let K • be a strong update operator, let L and U be uniformly improvable value functions, let s be a state, and let d * = (d U,1 , d L,2 ) be the current tentative NES at s. Then

width(K s V (s)) ≤ γ s P d U,1 ,d L,2 (s |s)width( V (s )),
where P •,• is naturally extended to mixed strategies (stochastic actions).

Proof. We have

width(K s V (s)) = width(H V (s)) (K s is strong) = HU (s) -HL(s) (def. of width(•)) = NEV(Γ s (U )) -NEV(Γ s (L)) (def. of H) = max d 1 min a 2 v U (s, d 1 , a 2 ) -min d 2 max a 1 v L (s, a 1 , d 2 ) = max d 1 min d 2 v U (s, d 1 , d 2 ) -min d 2 max d 1 v L (s, d 1 , d 2 ) = min d 2 v U (s, d U,1 , d 2 ) -max d 1 v L (s, d 1 , d L,2 ) ≤ v U (s, d U,1 , d L,2 ) -v L (s, d U,1 , d L,2 ) = γ s P d U,1 ,d L,2 (s |s)(U (s ) -L(s )) = γ s P d U,1 ,d L,2 (s |s)width( V (s )).
This result is important as it upper-bounds the width at s after update by a linear combination of the widths of the states immediately reachable from s through d * . Thus, sufficiently reducing the widths of those next states (which may change during execution) induces reducing the width at s. This serves to show both HSVI's and ShapleyGap's finitetime convergence.

Corollary 2. ShapleyGap converges in finite time to -optimal lower and upper bounds.

Proof. Let U i and L i denote the upper-and lower-bounding value functions after i iterations of ShapleyGap. Let us demonstrate by induction that U i -L i ∞ ≤ γ i U 0 -L 0 ∞ , until the termination criterion is reached. This property trivially holds for i = 0. Let us assume that it holds for some i ≥ 0. If U i -L i ∞ ≤ , then the termination criterion is reached. Otherwise, Lemma 2 can be applied at any state s such that U i (s) -L i (s) > , so that

U i+1 (s) -L i+1 (s) ≤ γ s P d U,1 ,d L,2 (s |s)width( Vi (s ))
(where d U,1 and d L,2 have been computed by the algorithm)

≤ γ s P d U,1 ,d L,2 (s |s)γ i U 0 -L 0 ∞ ≤ γ i+1 U 0 -L 0 ∞ .
For any other state, the gap is already less than (or equal to) . The property thus holds for i + 1. As a consequence, ShapleyGap converges in log γ ( / U 0 -L 0 ∞ ) iterations.

Theorem 1. The HSVI variant for zs-SGs specified abovethrough selection processes, update operators and trial stopping criterion-converges in finite time.

Proof. (sketch inspired by [START_REF] Smith | Probabilistic planning for robotic exploration[END_REF]) First, the previous lemma also holds when replacing the width by the excess [24, Lemma 6.2]. As a consequence, if all successors s of s reachable through d * are NEV-finished, then s is NEVfinished as well [START_REF] Smith | Probabilistic planning for robotic exploration[END_REF]Lem. 6.3]. Also, HSVI always selects an NEV-unfinished successor if one exists [START_REF] Smith | Probabilistic planning for robotic exploration[END_REF]Lem. 6.4], and all states beyond depth δ max def = log γ ( / U -L ∞ ) are NEV-finished [24, Lem. 6.4] (e.g., with U 0 and L 0 the initial bounds). A consequence is that any trial terminates and the penultimate visited state becomes NEV-finished [START_REF] Smith | Probabilistic planning for robotic exploration[END_REF]Lem. 6.7]. From this, the tree of reachable states from s 0 has bounded depth δ max and finite branching factor β, so that s 0 will be NEV-finished (at depth 0) after at most β δmax -1 β-1 trials.

The complete algorithm is detailed in Algorithm 2. As can be observed, the general algorithmic schema of HSVI is untouched as it essentially differs in (i) the action selection (relying on NESs) (lines 9-10), (ii) the next-state selection (lines 11), and (iii) the bound updates (relying on NEVs) (lines [START_REF] Bowling | Multiagent learning using a variable learning rate[END_REF][START_REF] Lagoudakis | Value function approximation inf zero-sum Markov games[END_REF]. Comparison with HSVI for POMDPs and POSGs: Note that the finite branching factor, due to the finite number of reachable states and despite the infinite set of actions, allows deriving a version of HSVI with the same definition of the excess function and the same convergence result (including the bound) as HSVI for POMDPs [START_REF] Smith | Probabilistic planning for robotic exploration[END_REF]. In the contrary, the potentially infinite branching factor in POSGs considered by [START_REF] Horák | Heuristic search value iteration for one-sided partially observable stochastic games[END_REF] and [START_REF] Horák | Solving partially observable stochastic games with public observations[END_REF] requires adding a term to the excess function, which induces an increased δ max , and relying on the Lipschitzcontinuity of the optimal value function to prove finite-time convergence to an -optimal solution.5

7 if width(s) > γ -δ then 8 Update (s) 9 d U,1 ← NES 1 (Γ s (U )) 10 d L,2 ← NES 2 (Γ s (L)) 11 s ∈ arg max s"∈S EE(s, d U,1 , d L,2 , s", δ)

G. Comparing HSVI, ShapleyGap, and ShapleyBR

ShapleyGap can be seen as in-between HSVI and Shap-leyBR since this variant of the Shapley (BR) algorithm shares the use of upper and lower bounds with HSVI. We here detail these similarities that imply similarities in the convergence behaviors.

a) Similarities between ShapleyBR and ShapleyGap: First, ShapleyBR and ShapleyGap both ignore the initial state s 0 , contrary to HSVI, and stop when a uniform criterion (satisfied by all states) is satisfied, while HSVI looks only at the gap at s 0 . Also, they will both adopt the same ordering of state updates (a rarely scrutinized factor), which may benefit (or, in the contrary, disadvantage) value propagation through states, and thus speed up (resp. slow down) the convergence process. HSVI, on its side, updates states along visited trajectories, so that not all states are visited, and not all visited states attain a (local) convergence criterion. Finally, ShapleyGap and ShapleyBR both use a priori initializations, while HSVI uses on demand initializations.

b) Similarities between ShapleyGap and HSVI: Compared to ShapleyBR, ShapleyGap and HSVI have not one, but two value functions to update, so that each state update is twice as expensive. Also, ShapleyBR will keep on updating all states at each iteration until it has converged, while ShapleyGap will stop updating states at which the gap is smaller than the required threshold, and HSVI will update only visited states if their gap is beyond a depth-dependent threshold. Finally, ShapleyGap and HSVI rely on the same value function initializations, so that they are likely to be both equally "lucky" (or "unlucky") compared to ShapleyBR and its different initialization.

To sum up, for a given problem instance, the same aforementioned features may be beneficial (or conversely detrimental) either to both ShapleyGap and ShapleyBR, or to both ShapleyGap and HSVI, so that one can expect ShapleyGap's results to often lie in-between ShapleyBR and HSVI.

H. Policy Execution

In the HSVI framework, 6 a player should act greedily with respect (i) to an optimistic bound of the optimal value function for the heuristic search to converge (cf. the action selection presented above), and (ii) to a pessimistic bound at execution time so as to guarantee the worst-case expected return. More precisely, at execution time, if in state s, player 1 (resp. 2) should find a Nash equilibrium strategy d L for Γ s (L) (resp. d U for Γ s (U )) and act according to d L,1 (resp. d U,2 ). That way, player 1 makes sure to get the security level value associated to Γ s (L). The following example illustrates why acting optimistically at execution time can be detrimental.

Example 1. Let us consider the matrix game Γ α described in Table II with its upper and lower bounds Γ up and Γ lo , all 3 games sharing the same NEV, 0. Yet, according to Γ up , any strategy (p, 1 -p) of (row) Player 1 (p ∈ [0, 1]) is part of a NES. If Player 1, being optimistic, plays (p, 1 -p) and Player 2, knowing that α is actually negative, plays (q, 1 -q), then the obtained value is pαq (≤ 0), i.e., a loss for player 1 if pq = 0.

This example also shows that Γ up and Γ lo having identical NEV does not mean that they are equal on the support of the tentative NE, i.e., the matrix values involved in the tentative

Γ up +1 0 0 0 ((p, 1 -p), (0, 1)) 0 Γ α α 0 0 0 [see text] 0 Γ lo -1 0 0 0 ( (
0, 1), (q, 1 -q)) 0 NE. Plus, while Γ α always has NEV 0, its possible NESs depend on whether α is negative, positive or null.

For player 1, this implies (i) either solving two-player normal form game Γ lo (s) when actually in state s at some point during execution, or (ii) being equipped with (a) a precomputed decision rule in each state s visited by zsSG-HSVI, and (b) a pre-computed or on-line-computable decision rule in any other reachable state (so as to guarantee the value associated to L's initialization). Under these circumstances, player 1 has an appropriate (γ -t -rational if at time t) decision to execute even in states not actually visited by the algorithm (likewise for player 2, but relying on U ), but reachable by non-trembling players. This also ensures that player 1 has appropriate-though not necessarily γ -t -optimal-decisions to execute even in states reached because player 2 acted suboptimally, in the sense that, if player 2's hand trembles in state s at t, then player 1's expected return from s remains at least L(s). Thus, zsSG-HSVI provides solutions strategies that are not near-optimal Markov perfect equilibrium, but are still robust to trembling hands.

Another consequence is that, while one could possibly exploit the fact that, if s and s are symmetric states, then U (s) = -L(s ), this requirement (being able to act according to a player's pessimistic bound) prevents us from exploiting the 0 NEV of self-symmetric states in symmetric zs-SGs, i.e., when both players' situations mirror each other.

V. EXPERIMENTS

The experiments compare zsSG-HSVI against ShapleyBR and ShapleyGap (presented in Sec. III-B) on various problems.

A. Setup a) Benchmark Problems: We have conducted experiments on (a) a two-player soccer board game [START_REF] Littman | Markov games as a framework for multiagent reinforcement learning[END_REF][START_REF] Lagoudakis | Value function approximation inf zero-sum Markov games[END_REF], parameterized by its dimensions w × h and the initial location of the Max player (x 0 , y 0 ) (the Min player being placed symmetrically); (b) a router/server flow control problem [START_REF] Altman | Flow control using the theory of zero-sum Markov games[END_REF][START_REF] Lagoudakis | Value function approximation inf zero-sum Markov games[END_REF], parameterized by the maximum buffer size bMax and initial buffer length bInit; (c) (discounted) Alesia, a prototypical war game [START_REF] Meyer | Learning strategies in games by anticipation[END_REF], parameterized by the radius R of the field and the two players' initial numbers of units (units); and (d) Alesia2, a novel variant where, at each time step, each player gets a reward equal to its (positive or negative) progress. γ was always set to 0.95 and to 0.001. These problems are detailed in Appendix C. b) Algorithms: HSVI, ShBR and ShGp denote the (zsSG-)HSVI, ShapleyBR and ShapleyGap algorithms for zs-SGs with trivial initializations (for ShBR: ∀s, V (s) = Rmax+Rmin 2(1-γ) ). Alg 1→2 (resp. Alg 2→1 ) denotes the (sequential) version of Alg ∈ {HSVI, ShBR, ShGp} where player 1 (resp. 2) moves first, obtained by simply replacing the Nash update operators by sequential ones, and, for HSVI, by letting player 1 (resp.

2) act greedily w.r.t. U (resp. L). These sequential versions have the same convergence properties as the "simultaneous" and MDP ones.

Finally, Alg+ denotes the version of Alg ∈ {HSVI, ShGp} where U (resp. L) is initialized with the upper-bound (resp. lower-bound) obtained with Alg 2→1 (resp. Alg 1→2 ) either a priori (if Alg = ShGp, with the same error ), or ondemand (if Alg = HSVI, with the same error γ -δ ). Note that we do not mix algorithm schemas. Also, ShapleyGap's stopping criterion relies on the local gap at s 0 , unless used as a (precomputed) initialization.

B. Results

The 3 sequential algorithms (player 1 moving first) and 3+2 simultaneous algorithms have been applied with a 3600s timeout on various instances of the 4 problems. All experiments have been conducted on a core i7 @ 1.9GHz with 4GB maximum heap size, using IBM CPlex to solve LPs. The Java source code is available at https://buffet.gitlabpages. inria.fr/HS4SG/ . Table III presents the results obtained on a subset of instances in terms of time to convergence, number of playouts (for HSVI) or iterations (ShGp/BR), and number of states visited at least once (error at s 0 is ≤ 0.001). Table IV presents results on the hard instances of the Soccer problem, adding the final error at s 0 .

Note that, in HSVI variants, the number of playouts (P ) is a number of generated trajectories, and thus should not be compared with the number of iterations in ShGp and ShBR variants (I).

1) Sequential Games: In the sequential case, HSVI 1→2 is often dominated by ShBR 1→2 and ShGp 1→2 on small problem instances. In the contrary, HSVI 1→2 appears to be dominating ShBR 1→2 and ShGp 1→2 on the largest problem instances (except on two Soccer problem instances that require visiting a large portion of the state space so that HSVI's natural pruning is not useful). An explanation is that, while only trivial initializations are used, HSVI 1→2 usually ignores many states, which often allows for faster convergence. On some overly large problems, this even prevents HSVI 1→2 from experiencing the out-of-memory errors of its competitors. In any case, i.e., regardless whether HSVI 1→2 is better or worse than ShGp 1→2 and ShBR 1→2 , ShGp 1→2 's convergence time is often in-between that of HSVI 1→2 and ShBR 1→2 (to put it differently, ShGp 1→2 is rarely better than both HSVI 1→2 and ShBR 1→2 , or by a small margin), which was expected, as discussed in Sec. IV-G. As can be noted, some problem instances need few iterations to converge, whatever the algorithm: In the largest instances of Alesia, this is due to the possibility for player 1 to easily defend itself and draw. 2) Simultaneous Games: Similar observations can be made while comparing HSVI, ShGp and ShBR, often (but not always) with comparable numbers of iterations and of visited states, though with much longer convergence times. The main difference thus seems to be due to the time consumption of the LP-based operator.

Let us now consider the versions with not-so-trivial initializations based on the sequential problems. ShGp+ usually performs a bit fewer iterations than its counterpart ShGp, but only saves time in FlowControl, and loses time in some other problems. HSVI+ may perform fewer or much fewer iterations than HSVI, sometimes a single one because the initial U and L are equal. Yet, except in these cases, the total running time can be much slower in HSVI+ than in HSVI (due to the many calls to HSVI 1→2 and HSVI 2→1 , which do not appear in the table). The contrast can be observed by looking at results obtained on Alesia vs Alesia2. Thus, while relying on a heuristic search is clearly beneficial on large problem instances, whether to use HSVI or HSVI+ depends on the problem at hand. Note also that no runs have been interrupted due to numerical instabilities when solving LPs, which happens when using a different LP solver (see also [START_REF] Buro | Solving the Oshi-Zumo game[END_REF]).

VI. CONCLUSION AND FUTURE WORK

The present paper proposes zsSG-HSVI, a heuristic search algorithm for discounted (two-player) zero-sum stochastic games with cycles, and non-zero rewards in any transition. The players' opposite criteria naturally led to algorithms with upper and lower bounds such as HSVI and BRTDP. The principle of optimism in the face of uncertainty is maintained, as well as that of acting (at execution time) according to the pessimistic bound. As the original HSVI, on which it is based, the resulting algorithm provably converges to an -optimal solution in finite time. To make the picture more complete and better analyze zsSG-HSVI, a variant of Shapley's algorithm is also introduced that, as zsSG-HSVI, maintains upper and lower bounds of the optimal value function and stops when the gap in-between them is below some threshold.

Experiments demonstrate that using zsSG-HSVI rather than Shapley-BR may be detrimental on small problem instances, but the benefit increases with the problem size. Also, Shapley-Gap's perfomance is typically in-between zsSG-HSVI and Shapley-BR, whichever of the two converges faster, which was expected as it mixes features of both other algorithms.

We now list several directions for future work. a) Improvements: LPs could be solved faster by using oracle methods (as in DOαβ [START_REF] Bošanský | Algorithms for computing strategies in two-player simultaneous move games[END_REF]) and/or bootstrapping techniques (because similar LPs are solved when re-visiting a state). A still open question how to handle heuristic initializations: which algorithms to use and with what precision (depending on whether pre-or on-demand computations are performed). Of course, other algorithmic schemes than HSVI could be employed, typically based on the FIND-and-REVISE schema [START_REF] Bonet | Faster heuristic search algorithms for planning with uncertainty and full feedback[END_REF], so that the main convergence results may be addressed jointly.

b) General-Sum SGs: A direction for future research is to extend the present work to solving general-sum SGs (with possibly more than two players). This expectedly means maintaining upper and lower bounds for each player. But a first issue is that of choosing an appropriate solution concept, since a given matrix game does not have a single NE value any more. If planning for all players at once-i.e., assuming each will commit to the strategy assigned to him-, then any NE may be a valid solution. But what if planning for a single player without constraints on the other players' strategies? c) POSGs: As mentioned in Sec. II, HSVI has been first directly applied to particular zero-sum (two-player) partially observable stochastic games (zs-POSGs): with one-sided partial observability [START_REF] Horák | Heuristic search value iteration for one-sided partially observable stochastic games[END_REF] and with public observability [START_REF] Horák | Solving partially observable stochastic games with public observations[END_REF]. These problems allow (i) not having to deal with nested beliefs, and (ii) reasoning about beliefs such that the optimal value function is convex/concave in belief-space, which allows defining generalizing value function approximators (upperand lower-bounds) as in POMDPs.

In contrast, an objective of the present work is to pave the way to addressing general POSGs using a variant of HSVI and value function approximation as already done for Dec-POMDPs [START_REF] Dibangoye | Optimally solving Dec-POMDPs as continuousstate MDPs[END_REF], i.e., using a sufficient statistic of the planner called an occupancy state. In the case of a 2-player zero-sum POSG, this means addressing the problem as an occupancy zs-SG [START_REF] Buffet | On Bellman's optimality principle for zs-POSGs[END_REF]. Then, the planning problem becomes deterministic, but the state and action spaces are continuous, thus infinite: one because it is a probability simplex, the other because it contains all stochastic decision rules. Taking inspiration from [START_REF] Horák | Heuristic search value iteration for one-sided partially observable stochastic games[END_REF][START_REF] Horák | Solving partially observable stochastic games with public observations[END_REF], one shall be able to achieve -optimal convergence in finite time using recursive partitioning and exploiting the Lipschitz continuity of the value function [START_REF] Fehr | ρ-POMDPs have Lipschitz-continuous -optimal value functions[END_REF].

APPENDIX A SHAPLEY ALGORITHMS

The classical Shapley algorithm [START_REF] Shapley | Stochastic games[END_REF], here called Shap-leyBR, is depicted in Algorithm 3, while the proposed Shap-leyGap algorithm is depicted in Algorithm 4. With ShapleyBR, an -optimal joint policy is obtained when both players act greedily with respect to V . With ShapleyGap, an -optimal joint policy is obtained when (maximizing) Player 1 acts greedily w.r.t. L, and (minimizing) Player 2 acts greedily w.r.t. U . TRIV : trivial approximations, e.g., ∀s, U (s) = 1 1-γ max s ,a 1 ,a 2 r(s , a 1 , a 2 ) and L(s) = 1 1-γ min s ,a 1 ,a 2 r(s , a 1 , a 2 ). Within Table V, the operators within some box (in-between two lines) return "greater or equal" functions than the operators within a lower box. Within the two boxes containing three operators, the only known ordering relations are:

G U ORA V ≥ G U MDP V and G L MDP V ≥ G L ORA V.
Of course, one issue is whether deriving these bounding value functions is worth the computational effort. The fixed points of the G • TRIV operators can be computed in constant time (see above formulas), and can serve as initializations for computing the fixed points of the other operators, e.g., again by heuristic search. The G • ORA operators are not worth considering as they would provide loser bounds than other operators at the same computational cost.

APPENDIX C BENCHMARK PROBLEMS

The present section provides details on the benchmark problems used in the experiments. They may differ from the

(G U TRIV V )(s) = max s ,a 1 ,a 2 ,s" r(s , a 1 , a 2 ) + γV (s") (G U ORA V )(s) = E a 2 ∼Unif(A 2 ) max a 1 Γ s (V )(a 1 , a 2 ) (G U MDP V )(s) = max a 1 E a 2 ∼Unif(A 2 ) Γ s (V )(a 1 , a 2 ) (G U SEQ V )(s) = min a 2 max a 1 Γ s (V )(a 1 , a 2 ) (HV )(s) = min d 2 max a 1 Γ s (V )(a 1 , d 2 ) = NEV(Γ s (V )) = max d 1 min a 2 Γ s (V )(d 1 , a 2 ) (G L SEQ V )(s) = max a 1 min a 2 Γ s (V )(a 1 , a 2 ) (G L MDP V )(s) = min a 2 E a 1 ∼Unif(A 1 ) Γ s (V )(a 1 , a 2 ) (G L ORA V )(s) = E a 1 ∼Unif(A 1 ) min a 2 Γ s (V )(a 1 , a 2 ) (G L TRIV V )(s) = min s ,a 1 ,a 2 ,s" r(s , a 1 , a 2 ) + γV (s")
original versions in the choice of certain parameters, in the use of a discount factor, and in the possibility of resetting (rather than ending in a terminal state).

A. Two-Player Soccer Game

This description (of the present implementation) is largely inspired by Lagoudakis and Parr [START_REF] Lagoudakis | Value function approximation inf zero-sum Markov games[END_REF], itself inspired by Littman [START_REF] Littman | Markov games as a framework for multiagent reinforcement learning[END_REF].

The playground is a w × h rectangular grid representing an horizontal soccer field: player 1 tries to score by getting out of the grid with the ball through its left side (and respectively through the right side for player 2). Each player is on his own cell, cell coordinates being noted (x, y) ∈ {1, . . . , W } × {1, . . . , H}. The ball is always possessed by one of the 2 players. The initial location of the Max player is (x 0 , y 0 ), the Min player being placed symmetrically.

Each player has a choice of 5 actions: up (U), down (D), left (L), right (R), and stand (S). At each time step the players decide on which actions they are going to take and then a fair coin is flipped to determine which player moves first. The players move one at a time in the order determined by the coin flip.

• If a player collides with a border or with another player during a move, the player remains in his current position. • If the player with the ball (attacker) runs into the opponent (defender), the ball is passed to the opponent. • Therefore, the only way for the defender to steal the ball is to be in the square into which the attacker intends to move. • The attacker can cross the goal line and score into the defender's goal, however the players cannot score into their own goals. Scoring for player 1 (resp. 2) results in an immediate reward of +1 (resp. -1) and a restart of the game. The discount factor for the problem is set to γ = 0.95, which encourages early scoring.

In Soccer, the number of states is:

|S| = (w • h) • (w • h -1) • 2 + 2.

B. Flow Control

This description of the Router/server flow control problem is largely inspired by Lagoudakis and Parr [START_REF] Lagoudakis | Value function approximation inf zero-sum Markov games[END_REF], itself inspired by Altman [START_REF] Altman | Flow control using the theory of zero-sum Markov games[END_REF].

A router is trying to control the flow of jobs into a server buffer (of maximum buffer size bMax and initial buffer length bInit) under unknown, and possibly changing, service conditions. This problem can be modeled as an MDP with the server being an uncertain part of the environment. However, to provide worst-case guarantees the router can view the server as an opponent that plays against him. This viewpoint enables to router to adopt control policies that perform well under worst-case/changing service conditions.

The system state is described by the current length of the buffer. Available actions are:

• for the router: low (L) and high (H), corresponding to a low (P A L ) and a high (P A H ) probability of a job arrival to the buffer at the current time step, with 0 < P A L < P A H ≤ 1; • for the server: low (L) and high (H), corresponding to a low (P D L ) and a high (P D H ) probability of a job departure from the buffer at the current time step, with 0 ≤ P D L < P D H < 1. Once the agents have picked their actions, the size of the buffer is adjusted to a new state according to the chosen probabilities, and the game continues.

The immediate cost R(s, a, o) for each transition depends on the current state s and the actions a and o of the agents: R(s, a, o) = c(s) + α × P A a + β × P D o , where c(s) is a real non-decreasing convex function, α ≤ 0, and β ≥ 0. c(s) is related to the holding cost per time step in the buffer, α is related to the reward for each incoming job, and β is related to the cost for the quality of service. The router attempts to minimize the expected discounted cost, whereas the server strives to maximize it. The discount factor is set to γ = 0.95. Under these conditions, the optimal policies can be shown to have an interesting threshold structure, with mostly deterministic choices and randomization in at most one state [START_REF] Altman | Flow control using the theory of zero-sum Markov games[END_REF]. However, the exact thresholds and probabilities cannot be easily determined analytically from the parameters of the problems which might actually be unknown. These facts make the problem suitable for learning with function approximation. We tested our method on a buffer of length 100 with: P A L = 0.2, P A H = 0.9, P D L = 0.1, P D H = 0.8, c(s) = 10 -4 s 2 , α = -0.1, β = +1.5. With these settings neither a full nor an empty buffer is desirable for either player. Increasing the buffer size beyond 100 does not cause any change in the final policies, but will require more training data to cover the critical area (0-100).

In FlowControl, the number of states is:

|S| = bMax + 1.

C. Alesia

This description of the Alesia game-illustrated by Fig. 1is largely inspired by Meyer et al. [START_REF] Meyer | Learning strategies in games by anticipation[END_REF].

In this game, also known as "Footsteps", "Citadel" or "Quo Vadis?" [START_REF] Morris | Evolving strategies for the game footsteps[END_REF], two citadels, each belonging to one player, are Fig. 1: Alesia's game field/board (copied from [START_REF] Meyer | Learning strategies in games by anticipation[END_REF]) placed at distance D = 2R + 1 from each other. A mark is initially placed in-between the citadels (in the middle). Each player starts with 50 units (input parameter units).

At each time step, both players simultaneously bid/engage (and definitely consume) some of their remaining units (at least 1 unit). The player with the highest bid pushes the marker one distance unit towards the opponent's citadel. In case of equal bids, the marker does not move.

A player wins if he manages to move the marker to the adversary's citadel. Otherwise it is a draw. A win (respectively a loss) leads to a reward of +1 (resp. -1).

In Alesia, the number of states is:

|S| = (2 • R + 1) • (units + 1) 2 .
Note: See also Oshi-Zumo (japanese for "pushing wrestler") [START_REF] Buro | Solving the Oshi-Zumo game[END_REF], which is very similar, or the paper game Tennis. 7 Alesia2: Soccer and Alesia share strong similarities as, in both cases, players are on the same field/playground and each would like to reach one side while confronting the other player. In both cases, a large part of the state space has to be covered for the value function to converge, even with a heuristic search algorithm, due to non-zero rewards being given only when a player reaches his target end of the field. In Alesia2, at each time step the instant reward corresponds to the x position of the "pack". As a consequence, one does not need to cover a large part of the state space to find optimal strategies for both players.

Algorithm 1 : 1 Fct HSVI ( ) 2 Initialize L and U 3 while 4 RecursivelyTry 6 Fct 8 Update (s) 9 a 12 Update (s) 13 return 14 Fct 15 L 16 U

 112346891213141516 Heuristic Search Value Iteration(in red: lines that will differ in the contributed algorithm) (U (s 0 ) -L(s 0 )) > do RecursivelyTry (s, δ) 7 if (U (s) -L(s)) > γ -δ then * ∈ arg max a∈A r(s, a) + γ s P a (s |s)U (s ) 10 s ∈ arg max s"∈S excess(s", δ) 11 RecursivelyTry (s , δ + 1) Update (s) ← Update (L, s) ← Update (U, s)

Algorithm 2 : 1 Fct HSVI ( ) 2 Initialize L and U 3 while

 2123 zsSG-HSVI (in red: differences with HSVI) width(s 0 ) > do 4 RecursivelyTry (s 0 , δ = 0) 5 return L 6 Fct RecursivelyTry (s, δ)

12 RecursivelyTry 16 L 17 U

 121617 ← Update (L, s) / * uses N E V(Γ s (L)) * / ← Update (U, s) / * uses N E V(Γ s (U )) * /

Algorithm 3 : 5 for s ∈ S do 6 v ← V (s) 7 V 8 BR 9 until BR ≤ θ 10 return V Algorithm 4 : 1 Fct 2 repeat 3 gap ← 0 4 for s ∈ S do 5 if 6 L 7 U 9 until gap ≤ 10 return

 3567891041234567910 ShapleyBR (asynchronous) 1 Fct ShapleyBR ( ) input : V initialized (randomly or otherwise) output: (s) ← Update (V, s) ← max{BR, |V (s) -v|} ShapleyGap (asynchronous) ShapleyGap ( ) input : L and U lower and upper initializations output: L and U -optimal lower and upper bounds U (s) -L(s) > then (s) ← Update (L, s) (s) ← Update (U, s) 8 gap ← max{gap, width (s)} (L, U ) APPENDIX B UPPER AND LOWER BOUND INITIALIZATIONS

TABLE I :

 I Various update operators for the value function, ordered by resulting value. Top: 2 operators for initializing U . Middle: optimal Shapley operator. Bottom: 2 operators for initializing L.

TABLE II :

 II An example game Γ α (α ∈ [-1, +1]) with example upper and lower bound games Γ up and Γ lo , their NESs and their (NE) values.

	game	matrix	NESs	value

TABLE III :

 III Running time (in seconds), number of playouts (P ), iterations (I) and visited states (N ) for easy instances of the Soccer problem, and various instances of the FlowControl, Alesia, and Alesia2 problems, solved with serialized and simultaneous versions of HSVI, ShGp and ShBR, using γ = 0.95 and = 0.001. In bold, shortest convergence times (distinguishing sequential and simultaneous games).

	Algorithm →		HSVI 1→2		ShGp 1→2	ShBR 1→2		HSVI			HSVI+		ShGp		ShGp+		ShBR
	Problem	|S|	t	P	N	t	I	t	I	t	P	N	t	P	N	t	I	t	I	t	I
	w h x 0 y 0	[ Soccer ]
	5 4 0 0 762	3 2148 762	1 128	0	5	56 656 759	16	79 223	10 26	10 25	2 11
	5 4 0 1 762	4 2225 762	1	75	0	5	58 717 761	16	96 229	11 26	10 25	2 11
	5 4 1 0 762	0	89 270	0	4	0	5	4	42 123	0	1	0	2	4	2	3	2 11
	5 4 1 1 762	3 1799 762	0	75	0	5	62 704 761	17	94 228	10 25	9 24	2 11
	5 4 2 0 762	0	51 156	0	3	0	5	2	27	89	0	1	0	1	3	1	2	2 11
	5 4 2 1 762	0	78 233	0	3	0	5	4	47 116	0	1	0	1	3	1	2	2 11
	5 4 3 0 762	0	15	50	0	2	0	5	0	6	14	0	1	0	1	2	1	1	2 11
	5 4 3 1 762	0	20	56	0	2	0	5	0	8	20	0	1	0	1	2	1	1	2 11
	5 4 4 0 762	0	1	2	0	1	0	5	0	1	2	0	1	0	1	1	0	0	2 11
	5 4 4 1 762	0	1	2	0	1	0	5	0	1	2	0	1	0	1	1	0	0	2 11
	10 6 0 0 7.1K	19 14036 7.1K	6	78	0	10	588 6169 7.1K	64 175 1.3K	118 34	116 33	29 18
	10 6 0 2 7.1K	20 13399 7.1K	6	77	0	10	598 6320 7.1K	78 245 1.6K	118 34	116 33	29 18
	10 6 4 0 7.1K	2	523 2.3K	1	6	0	10	89 798 3.3K	2	1	0	24	6	21	5	29 18
	10 6 4 2 7.1K	20 10725 7.1K	4	59	0	10	649 6644 7.1K	72 166 1.2K	108 29	103 28	29 18
	10 6 8 0 7.1K	0	15	73	0	2	0	10	0	6	18	0	1	0	11	2	7	1	29 18
	10 6 8 2 7.1K	0	20	75	0	2	0	10	0	8	16	0	1	0	10	2	7	1	29 18
	bMax bInit	[ FlowCtrl ]
	100	10 101	0	130	78	0 181	0	98	18 129	77	0	1	1	8 181	7 168	2 98
	100	90 101	0	130	78	0 181	0	98	18 129	77	0	1	1	8 181	7 168	2 98
	500	10 501	0	177	99	0 237	0 238	33 156 138	0	1	0	50 237	33 165	24 238
	500	90 501	0	177	99	0 237	0 238	33 156 138	0	1	0	48 237	34 165	25 238
	1000	10 1.1K	0	220 118	0 262	0 264	40 175 133	1	1	0	107 262	67 165	53 264
	1000	90 1.1K	0	220 118	0 262	0 264	40 175 133	0	1	0	106 262	68 165	53 264
	5000	10 5.1K	0	294 103	3 319	2 322	64 233 173	1	1	0	647 319	334 165	332 322
	5000	90 5.1K	0	294 103	3 319	2 322	64 233 173	1	1	0	648 319	334 165	324 322
	R units	[ Alesia ]
	2	8 405	0	54 135	0	1	0	3	0	63 126	0	10	15	0	3	0	2	0	4
	3	14 1.6K	0	228 702	0	2	0	6	2 297 653	0	23	72	3	4	3	3	3	7
	4	20 4.0K	0	550 2.1K	0	3	0	8	9 760 2.0K	3	90 310	13	6	13	5	9 10
	5	27 8.7K	2 1232 4.8K	1	3	2	11	30 1782 4.7K	12 221 931	46	8	38	7	29 13
	6	33 16K	5 2175 8.9K	5	4	8	14	75 3244 8.6K	32 310 1.6K	100 10	96	9	65 15
	7	40 26K	15 3598 16K	12	4	23	16	185 5497 16K	76 397 2.6K	210 11	204 10	145 18
	50	30 98K	0	58 1.8K	11	1	99	30	28 1424 5.7K	0	1	0	580	9	531	8	795 30
	60	35 157K	0	68 2.4K	25	1	252	35	49 1969 8.2K	0	1	0	1096 10	1039	9 1584 35
	70	40 238K	0	78 3.2K	53	1 571	40	77 2646 11K	1	1	0 1973 11 1930 10 2973 40
	R units	[ Alesia2 ]
	2	8 405	0	68 138	0	1	0	3	0	97 161	0	24	42	0	4	0	2	0	4
	3	14 1.6K	0	281 708	0	1	0	6	3 417 758	2 145 300	5	6	3	3	3	7
	4	20 4.0K	0	592 1.9K	0	2	0	8	12 1092 2.1K	9 467 941	17	8	12	5	10	9
	5	27 8.7K	1 1119 4.1K	1	2	2	10	32 2285 4.6K	31 1015 2.4K	52 10	40	7	27 11
	6	33 16K	2 1887 7.4K	4	3	6	12	71 4021 8.1K 102 1968 4.4K	118 12	100	9	63 13
	7	40 26K	5 2800 13K	9	3	20	14	181 7006 14K 279 3372 7.9K	240 13	237 11	139 15
	50	30 98K	2 2082 8.7K	32	5	95	30	61 2901 8.3K	69 1625 4.6K	934 14	817 11	959 30
	60	35 157K	5 3046 14K	87	6 244	35	104 4320 13K	165 2686 7.7K 1838 16 1563 12 1940 35
	70	40 238K	11 4155 21K	194	6 570	40	204 6127 19K	332 3697 12K	3419 18 2857 13 3600 40

TABLE IV :

 IV Running time (in seconds) with a 3600s timeout (TO), number of playouts (P ), iterations (I) and visited states (N ) for hard instances of the Soccer problem, solved with serialized and simultaneous versions of HSVI, ShGp and ShBR, using γ = 0.95 and = 0.001. In bold, shortest convergence times (distinguishing sequential and simultaneous games), or timeout with smallest error in s0 (e).

	Algorithm →			HSVI 1→2		ShGp 1→2		ShBR 1→2		HSVI			HSVI+	ShGp		ShGp+		ShBR
	Problem	|S|	t	P	e	N	t I	e	t I e	t	P	e	N	t P	e N	t I	e	t I	e	t I	e
	w h x0 y0	[ Soccer ]
	50 30 0 15 4.5M	TO 1.2M .13 3.5M	TO 53 0.05 1550 50 0	TO 23.8K 1.2 138K TO 1 1.1 0 TO 1 1.3 TO 0 1.3 TO 3 34.3
	50 30 15 15 4.5M	TO 1.2M .29 3.5M	TO 54 0.02 1580 50 0	TO 24.6K 1.4 174K TO 1 1.1 0 TO 1 1.1 TO 1 1.0 TO 3 34.3
	50 30 30 15 4.5M	560 0.2M	0 1.1M 1407 20	0 1566 50 0	TO 24.7K 1.3 176K 964 1	0 0 TO 1 1.0 TO 1 .98 TO 3 34.3
	100 60 0 30 72M	TO 1.2M .18 4.9M	--out of memory --	TO 24.0K 1.2 188K TO 1 1.1 0	--out of memory --
	100 60 30 30 72M	TO 1.1M .37 8.0M	--out of memory --	TO 24.6K 1.4 253K TO 1 1.2 0	--out of memory --
	100 60 60 30 72M	TO 1.2M .38 8.9M

--out of memory --TO 24.6K 1.3 255K TO 1 1.2 0 --out of memory --

Table I

 I only presents a limited selection of operators that can be used to compute upper and lower bounds of the optimal value function. For completeness, Table V shows an extended list of candidate operators for both bounds, which we also describe with words as follows: G game approximation-also known as serialization-, i.e., U being the optimal value if player 1 acts before player 2, and L the opposite (the second player knowing the action choice of the first player); G

		[L/U ]
		[L/U ] MDP : an MDP approximation, i.e., U (respectively L) being
		the optimal value function of the MDP induced by
		assigning to player 2 (resp. player 1) any fixed strategy-
		e.g., random actions;
	G	[L/U ] ORA : an MDP approximation with an oracle that predicts
		the action of the random opponent (but not nature's
		move); or
	G	[L/U ]

SEQ

: a sequential

TABLE V :

 V Various update operators for the value function, almost ordered by resulting value. In the middle is the optimal Shapley operator. Above are operators for initializing the upper bound U . Below are operators for initializing the lower bound L.

As Shapley[START_REF] Shapley | Stochastic games[END_REF], we do not account for the pay-off relevance of states.

Churchill et al. [21] do so with an αβ-based algorithm, thus not dealing with cycles and infinite horizons.

One could possibly derive a bound on the number of iterations before convergence for these POSGs, but this would involve results related to hypersphere packing, as well as the volume of both an hypersphere and a regular simplex.

This discussion also holds for ShapleyGap because of the use of upper and lower bounds.

c 2020 IEEE / TRANSACTIONS ON GAMES / DOI: 10.1109/TG.2020.3005214

This work was supported by the French National Research Agency through the "Planning and Learning to Act in Systems of Multiple Agents" Project under Grant 19-CE23-0018-01. (Buffet.)


Martin Erb
email: martin.erb@trugraz.at

Christian Steger
email: steger@trugraz.at

Martin Troyer
email: martin.troyer@trugraz.at

Josef Preishuber-Pflügl
email: j.preishuber-pfluegl@cisc.at

Trigger Alarm: A Smart NFC Sniffer for High-Precision Measurements

Keywords: Near Field Communication, Software Defined Radio, Measurement System, Test Platform, Interoperability

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Near Field Communication has experienced a steep marked ramp up in recent years. The rapidly increasing amount of mobile phones pushed to the global market led to the increasing integration of NFC technology in consumer electronic devices. NFC provides a convenient, easy, and secure possibility to transfer wireless data between two electronic devices [START_REF] Finkenzeller | RFID Handbook: Fundamentals and Applications in Contactless Smart Cards, Radio Frequency Identification and Near-Field Communication[END_REF][START_REF] Heinrich | RFID and beyond -growing your business through real world awareness[END_REF]. Integrating NFC, which has been evolved from the Radio Frequency Identification (RFID) technology, to smartphones enables the possibility to replace identity documents for access control or debit cards for payment [START_REF] Lacmanović | Contactless payment systems based on RFID technology[END_REF]. Furthermore, NFC allows initiating device connectivity such as Bluetooth or WLAN, thus allowing the user to easily exchange security-sensitive data between their devices [START_REF] Coskun | The Survey on Near Field Communication[END_REF][START_REF] Fischer | NFC in cell phones: The new paradigm for an interactive world [Near-Field Communications[END_REF][START_REF]Consumer Preference for Contacless Payment & Automated Ticketing Supported by Speed & Convenience Benefits Drives Demand for NFC Enabled Phones[END_REF][START_REF] Langer | Anwendungen und Technik von Near Field Communication (NFC)[END_REF][START_REF] Shobha | NFC and NFC payments: A review[END_REF].

To keep the NFC technology on the course of further success and to enlarge the influence to the market, the user acceptance needs to be increased. To achieve this and to encourage more people to use NFC-enabled devices for a wide range of different applications in their daily life, interoperability needs to be guaranteed. The ultimate goal is to achieve full interoperability among all devices from various manufactures. To reach this goal, the NFC Forum follows the approach of harmonizing the different standards and ensuring interoperability by extensive conformance testing [START_REF] Gsma | Joint Position Paper on Interoperability of NFC Mobile Devices[END_REF][START_REF]NFC Forum: The Keys to Truly Interoperable Communications[END_REF][START_REF]NFC Forum: ISO/IEC 14443 Analog Parameter Comparison and Alignment[END_REF]. However, interoperability testing cannot entirely be replaced by conformance testing because during the certification process one communication party is always simulated. Additionally, the setup for conformance testing has to be entirely defined to make the test procedure reproducible [13]. This leads to the drawback that conformance testing cannot represent all real-world scenarios and misses to include many user requirements [START_REF] Kang | Relating interoperability testing with conformance testing[END_REF][START_REF] Kindrick | Improving conformance and interoperability testing[END_REF]. The problem of missing user requirements is shown in various current systems where certified products have interoperability lacks [START_REF] Boada | Near Field Communication devices: having interoperability issues[END_REF]. In contrast to other wireless technologies where interoperability issues may occur due to interference [START_REF] Marinčić | Interoperability of iot wireless technologies in ambient assisted living environments[END_REF], such as Bluetooth or WiFi or test systems where the physical layer is excluded from testing [START_REF] Song | An interoperability test system for ieee 1451[END_REF], NFC interoperability test systems have to analyze the whole data transfer across all communication layers. CISC Semiconductor, a leading supplier of RFID measurement and test solutions, developed an automated interoperability test system to gain significant speedup for testing [START_REF]CISC Semiconductor Interoperability Website[END_REF]. In the case of a communication error, however, manual debugging with different additional measurement and analysis equipment is required. We analyzed projects over the last years from our research partners (CISC Semiconductor and NXP Semiconductors) and found out that setting up the measurement devices and performing additional communications to detect the error root cause consumes a massive amount of the overall test time. Lack of all-in-one solution. As defined by the NFC test standard [13], the sample rate of the measurement device to properly analyze communication parameters must be at least 500 MS/s. Existing test platforms such as presented by the works [START_REF] Erb | A Novel Automated NFC Interoperability Test and Debug System[END_REF][START_REF] Hawrylak | Automated Test System for ISO 18000-7 -Active RFID[END_REF][START_REF] Kun | Design and Development of a Open Frame RFID System Unite Test Platform[END_REF] have implemented protocol decoder and further analysis tasks based on the baseband signal. They use the baseband signal because the required bandwidth is only 847 kHz (the subcarrier generated by the Proximity Inductive Coupling Card (PICC)) plus the data rate such as 106 kHz used for payment applications. Therefore, a digital sample data rate of about 6 MS/s is sufficient to decode the protocol. Such measurement devices are essential and very useful for interoperability error debugging; however, not all communication relevant parameters can be analyzed. Therefore, an additional oscilloscope is still required, with which a test engineer can capture parts of the communication with a sufficiently high sample rate. To capture exactly the appropriate part of the communication mostly requires multiple tries to set up the oscilloscope.

The time to set up the measurement system correctly, perform the measurements again, and analyze the results prolongs the debug time and makes interoperability testing very expensive. Oscilloscope for specific parameters. The trigger functionalities of an oscilloscope are sufficient to analyze simple parameters like the field strength or modulation index. For such measurements, no specific parts of an NFC communication are required, which means that one configuration of the measurement is sufficient, and only one communication needs to be performed per measurement point. In work [START_REF] Langer | A comprehensive concept and system for measurement and testing Near Field Communication devices[END_REF] they present an automated test system with various measurement devices to analyze interoperability problems. In this case, the oscilloscope is used to measure the high frequency (HF)-field strength. Nevertheless, the system can analyze only the HF-field strength automatically. Otherwise, manual interaction from a test engineer would be required to reconfigure the oscilloscope, which would again increase the test and measurement time. Lack of intelligent trigger features. During conformance testing, one communication partner is always simulated, meaning the test controller is generating either a Proximity Coupling Device (PCD) command or a PICC response. Therefore, it is straightforward to control a high precision analog measurement device with a high sampling rate, such as an oscilloscope, to capture exactly the communication parts required to check if the Device Under Test (DUT) fulfills the requirements defined by the standards. This is not true for interoperability testing where both communication partners have finalized products and have to be handled as black-box. Additionally, interoperability testing mostly requires to analyze a specific command or response within the whole communication. However, it is time-consuming to configure the oscilloscope each time to capture exactly the required command or response using a sample rate of at least 500 MS/s. The high sample rate prevents the user from capturing the whole communication. Furthermore, the time between the start of the communication and the occurrence of a certain command may differ between multiple test runs due to re-transmissions. To the best of our knowledge no analog measurement system including such features to trigger an external high-precision oscilloscope exists. Our contribution. In this paper, we present a smart sniffer tool providing intelligent trigger functionality for NFC interoperability testing based on softwaredefined radio (SDR) platform. The sniffer tool presented does not close the gap of an all-in-one solution but implements intelligent trigger features for easy communication capturing using an external oscilloscope. Precise and easy triggering at the position before an error happens or where additional investigations should be made is essential to reduce the time for a manual debug session significantly. Therefore, we implemented three options for the communication types described in ISO-14443, which apply rising edges on different general-purpose input outputs (GPIO): (i) HF-field on, (ii) every command typeA or typeB, and (iii) selected command typeA or typeB. In Section 3, we present how the different trigger functionalities can be used to achieve significant speedup during testing. In this paper, we make the following contributions:

-We design three different trigger functionalities not yet used for interoperability testing to reduce the manual debug session duration (Section 1). -We implement the designed features based on an SDR platform, the LimeSDR (Section 2). -We experimentally show the functionalities and the performance of the three different trigger features (Section 3).

After describing related work in Section 4 we conclude our paper in Section 5, along with a discussion on future work.

1 Trigger Design As a basis for our Field Programmable Gate Array (FPGA) design, we used the work [START_REF] Erb | A Novel Automated NFC Interoperability Test and Debug System[END_REF] of the researcher from the University of Technology Graz. In their work, they implemented a simple HF-field on trigger using the RedPitay platform [START_REF]StemLabs: RedPitaya Website[END_REF]. Our design is not restricted to any hardware platform. However, the input to the trigger block is the absolute value of the baseband of the captured communication. Nevertheless, it makes sense to include the trigger functionality to a similar measurement device as the RedPitaya. Figure 2 shows a simplified version of the design of the trigger functionality. The green blocks show the input values enabling the possibility to configure the behavior of the trigger. The HF-on block and the Command Detection block show the two main components of the trigger. We split up the FPGA and the RF-transceiver because different FPGA hardware platforms may not include an RF-transceiver but, for sure multiple connection possibilities for an RF daughterboard.

RF-Transceiver

HF-on trigger. The HF-on trigger is the simplest version of a trigger and could also be realized using an oscilloscope. The HF-on trigger outputs a single rising edge on a GPIO pin when the absolute value exceeds the trigger level the first time after the user armed the trigger. The trigger level is configurable by the user. Implementing this simple trigger feature enables the possibility to synchronize the time between the captured I/Q data by the measurement device and the signal captured by the oscilloscope. This can be useful for further signal analysis tasks. Additionally, this trigger is internally connected to the streaming block. Meaning, the host PC starts receiving I/Q data from the measurement device when the HF-on trigger fires. This is useful during testing because, in most cases, a test engineer is not interested in the signal before a communication start. Command based trigger. The second trigger functionality is based on command recognition. The user can configure the communication type and the number of the command when the trigger should fire. For simplicity, only the number of the command can be defined because triggering on a specific command name would require a complete protocol decoder implemented on the FPGA. The command detection block is responsible for finding all commands, either typeA or typeB, within the absolute value of the baseband signal and counting them. The trigger fires whenever the number of found commands of one single communication type is equal to the configured value by the user. If the user does not define any number of commands to trigger on, typeA and typeB trigger fire on every detected command. The command base trigger feature is handy and time saving for a test engineer when it comes to capturing a specific command within a communication. If an interoperability issue should be analyzing the error mostly happens in the same position within the protocol, but not at the same time after the communication start. Therefore, a standard oscilloscope trigger would not be sufficient to always trigger at the correct point in time. The functionality where every command triggers a rising edge significantly simplifies error cases where either the PCD waits for a response of the PICC or the PICC does not understand the command. In these cases, the oscilloscope shows the last command sent by the PCD and can easily be analyzed by a test engineer.

Trigger

Implementation

Hardware

Before thinking of implementation details, we used the design described in Section 1 to find a suitable hardware platform to implement our smart sniffer. As mentioned above, the absolute value of the baseband signal is required as input for the trigger function. NFC technology uses a 13.56 MHz carrier frequency and a sub-carrier with a frequency of 848 kHz. For our implementation, we are focusing on the payment application, which supports a data rate of 106 kBit/s, but the hardware should support higher data rates too. During our research, we tried to focus on only a few important hardware requirements: (i) Radio Frequency (RF)-front end capabilities such as center frequency, bandwidth, and sample rate, (ii) FPGA specification, (iii) configurable GPIOs, and (iv) connection interface to the host PC. Because we are using only the baseband of the signal, we decided to use a sample rate of about 10 MS/s for the I/Q data transmitted to the host PC. Therefore, the data throughput of the connection interface between measurement hardware and host PC is not critical, and a lot of different hardware platforms are available. After our evaluation phase, we decided to use the LimeSDR from Lime Microsystems [20] in the USB configuration. The advantage of this hardware platform is the powerful RF-transceiver chip, which includes already highly configurable analog and digital signal processing units. These units enable the possibilities to shift the signal to the baseband and to apply the required filters to have clean I/Q data ready even before sent to the FPGA. Using such a powerful RF-transceiver chip saves many hardware resources on the FPGA for other tasks. The FPGA provides enough computational power and memory resources to implement the trigger features described in Section 1. The LimesSDR provides a USB 3.0 interface to connect the host PC. The data throughput of this interface is far enough to transfer the I/Q data shifted to the baseband.

Software

Figure 1 shows the high-level block diagram of our FPGA implementation. The sniffer coil is connected to the RF-front end and placed between PICC and PCD. The signal processing units of the RF-transceiver convert the captured communication to the digital domain and shift the signal to the baseband. Furthermore, the RF-transceiver applies the corresponding filters and sends the I/Q data to the FPGA. Further, the FPGA sends the captured baseband I/Q data to the USB-Out interface and computes the absolute value of the signal. As shown in Figure 1, the calculated absolute value is than used as input for the three different main functional blocks of the FPGA implementation: (i) HF-on detection, (ii) command detection typeA and typeB, and (iii) command count. The HF-on detection block compares the received absolute value with the trigger level defined by the user using the configuration register. The first time the absolute value exceeds the threshold, the HF-on trigger fires a rising edge on GPIO Pin1. Additionally, this trigger signal is used to start the I/Q data streaming to the USB-Out interface, more precisely to the host PC. This feature gives a lot of flexibility during testing. It reduces the data to be transferred because the unwanted signal before a communication start is not sent to the host PC. Furthermore, this trigger allows a precise synchronization between captured I/Q data on the host PC and the recorded data on an external oscilloscope. The command detection blocks for typeA and typeB use a min-max method with fixed thresholds based on the modulation values defined in the standard to detect rising edges within the received signal. Using the peak-to-peak values and the frequency of the rising edges, the detector blocks check if the absolute value belongs to a request sent by the PCD or not. If one of the detection blocks identifies a command, it increases the command count by one. The command count block counts the number of commands for a single type, which has been decoded after the acquisition has been started. The count of recognized commands is further compared with the number defined by the user in the configuration register. If the number counted by the command count block is equal as configured by the user, GPIO Pin2 is set to high for typeB and GPIO Pin3 for typeA, respectively. If the user configures the number of commands with zero, a short peak is applied to the corresponding GPIO pin whenever a command is detected. For our use case, which is the payment application, the data rate is always 106 kBit/s. Therefore, the communication between PCD and PICC takes place via Amplitude Shift Keying (ASK) 10 % amplitude modulation of the RF operating field for communication typeB and around 100 % for typeA. This is not true for data rates higher than 424 kBit/s for which the thresholds for the min-max method need to be adapted. As depicted in Figure 1 the different trigger features are implemented in parallel. This means that the HF-on trigger can be used simultaneously to the different command detection features. Therefore, a test engineer can configure the oscilloscope in a way that triggers first on the HF-on trigger to show the start of the communication and later trigger again if a certain amount of commands were detected. This increases the flexibility of performing manual measurements using an oscilloscope and reduces the amount of required additional communications because multiple events can be observed at once.

Evaluation

We used the design described in Section 1 to implement the functionality as presented in Section 2 and performed an evaluation shown in this section. We used one PCD and two PICCs to show the trigger functionalities for communication typeA and typeB. The three NFC-enabled devices implement the payment application according to the EMVCo standard. Therefore, they are communicating at 106 kBit/s. As shown in Figure 3, we placed the sniffer coil, which is connected to the LimeSDR and the oscilloscope, between PCD and PICC. The LimeSDR was connected to the host PC, which was responsible for configuring the device, controlling the measurement procedure as well as starting the communication on the PCD. Furthermore, we connected the three different GPIO pins of the LimeSDR to the remaining analog input channels of the oscilloscope. The trigger of the oscilloscope was configured in single-shot mode using one of the analog inputs as a trigger source. The sample rate of the oscilloscope was set to 2 GS/s. Figure 4 shows the beginning of an NFC communication between PCD and PICC using communication typeB. One can see the four captured signals by the oscilloscope: (i) HF signal capture by the sniffer coil, (ii) typeA trigger signal for typeA commands, (iii) typeB trigger signal for typeB commands, (iv) and HFon trigger signal when the HF-field exceeds the configured threshold. The fifth signal (SDR) shown in Figure 4 is the absolute value captured and processed by the LimeSDR. The LimeSDR was configured to trigger on HF-on and on the second typeA and typeB command. The five red marked frames show three zoom regions, explained more detailed later, and the shape of the commands for the different communication types.

The default activation procedure for payment transactions starts with the HF-field activation by the PCD shown in the first red marked frame Zoom 1. Afterward, the PCD tries to activate the card using a typeA command, as shown in the second red-marked frame TypeA cmd 1. The activation was not successful because we used a typeB only PICC, and therefore, no typeA response can be found. Further on, the PCD tries to activate the card using a typeB command, as shown in the third red marked frame TypeB cmd 1. This time one response after the command can be found. The default procedure of the PCD is to check again if a typeA card is present. Therefore, a second typeA command is sent thus marked with a red frame Zoom 2. Since the PICC did not respond to the second Figure 5 shows a close-up of the HF-on trigger functionality more precisely the Zoom 1 frame in Figure 4. On the time axis, one can observe that the oscilloscope triggered on the rising edge of the HF-on signals generated by the LimeSDR because time equals zero. The time delay between actual HF-field on captured by the oscilloscope and the rising edge of the signal generated by the LimeSDR of about 22 µs is introduced by the processing time of the implemented detection algorithm and the time required to control the GPIO pin. Nevertheless, this time delay is constant and thus can be used to synchronize the captured signal from the oscilloscope and the LimeSDR. All the different figures show the SDR signal synchronized to the HF signal using this time delay. As explained in Section 2, the streaming of the I/Q data to the host PC is started at the same time when the HF-on trigger fires. Figure 5, however, shows that the SDR signal (depicted in green) starts about 22 µs earlier. This feature was set as an additional requirement not to lose any important information and was realized using ring buffers for data streaming to the host PC.

Figure 6 shows an enlarged view of the LimeSDR command trigger for ty-peA. One can see that the rising edge of the command recognition appears after around 220 µs. The reason, therefore, is, on the one hand, the implemented command detection algorithm, which analyzes the whole command and waits until the command is finished to reduce the probability of wrong command detection. On the other hand, the ring buffer, which has to be bigger than for the HF-on trigger, and the overall processing time of the LimeSDR, is larger. The constant time shift between command end and the rising edge of the trigger can be ignored because conventional oscilloscopes have a changeable pre-trigger time. This measurement shows that a user can trigger very precisely on a predefined command even if the between communication start and the specified command changes. The last red marked frame in Figure 4 shows the second typeB command, specifically the command the LimeSDR triggers on. Figure 7 displays a close-up of the mentioned frame. One can see that the rising edge of the trigger signal from the LimeSDR is again 220 µs after the end of the command. This has, of course, the same reasons as explained in the previous paragraph. However, we tried to keep the time delay for both command triggers as similar as possible to ensure that the test engineer can use the same oscilloscope settings independent of the communication type. Figure 8 shows the last missing trigger functionality, applying a short peak to the appropriated GPIO for every command within the whole communication. For clarity reason, the HF-on trigger is not shown in this figure, but it can be used in parallel for this configuration case as well. This figure shows a typeA communication to prove further that the trigger functionalities work the same way for typeA communications. Observing Figure 8, one can see a short peak after each command of typeA and typeB captured by two different input channels of the oscilloscope. This shows that the test engineer can decide to configure the oscilloscope to trigger either on typeB or typeA commands. Using this feature, it is possible to quickly capture the last command independent of the length of the communication.

Figure 4 in combination with the three close-up figures 5, 6, and 7 shows that the three trigger functionalities work in parallel. Furthermore, it is proven that triggering on a specific command within a communication is possible. All these features enable the possibility of convenient high-precision communication snippet capturing using an external oscilloscope and, therefore, reduce the time for manual debug sessions.

Related Work

In the field of NFC testing, a lot of research already exists. Research dealing with measurement methods of various communication parameters, design, and imple-Fig. 8: TypeA Communication Trigger on all Commands mentation of test systems focusing on different NFC applications, and design of measurement devices to be as accurate as possible. Furthermore, the development of automated conformance and interoperability test systems is ongoing. Baseband measurement systems. For interoperability testing, first of all, it is essential to analyze the whole communication in general. However, for some specific communication relevant parameters, the baseband signal is not sufficient. The required information is lost during the mixing and filtering process. In the works [START_REF] Erb | A Novel Automated NFC Interoperability Test and Debug System[END_REF][START_REF] Hawrylak | Automated Test System for ISO 18000-7 -Active RFID[END_REF][START_REF] Kun | Design and Development of a Open Frame RFID System Unite Test Platform[END_REF], different hardware, and measurement methodologies are used to analyze the communication between two NFC-enabled devices regarding interoperability issues. These works have one thing in common: the complete signal analysis and error evaluation are based on the baseband signal. This can be very useful to find protocol errors or to analyze which communication partner led to the communication fault. Furthermore, it is helpful to find the position of the error within the communication quickly. However, it is not suitable to analyze specific parameters that require an exact representation of the HF-carrier signal of the PCD. To find all possible interoperability issues a high-precision oscilloscope is essential. Therefore, the designed trigger functionality presented in this paper could be used to improve the already existing functionality presented in [START_REF] Erb | A Novel Automated NFC Interoperability Test and Debug System[END_REF][START_REF] Hawrylak | Automated Test System for ISO 18000-7 -Active RFID[END_REF][START_REF] Kun | Design and Development of a Open Frame RFID System Unite Test Platform[END_REF] as long as the used hardware provides configurable GPIOs and enough computation power. Special setup. In contrast to conformance testing, where a well-defined measurement setup is required, this is not true for interoperability testing. The standard ISO/IEC 10373-6 [13] defines this specific setup, and it is taken over by the NFC-Forum in their analog parameter comparison and alignment [START_REF]NFC Forum: ISO/IEC 14443 Analog Parameter Comparison and Alignment[END_REF]. Since interoperability testing is performed as black-box testing with finished products, the specific setup and most of the given specifications of the various standards cannot be applied anymore. Furthermore, the algorithms for many parameter computations have to be adjusted [START_REF] Muehlmann | Automated analysis of iso/iec14443a interrogator command pulse shapes[END_REF][START_REF] Stark | How to guarantee phase-synchronicity in active load modulation for NFC and proximity[END_REF]. The presented approach in work [START_REF] Couraud | A very high bit rate test platform for ISO 14443 and interoperability tests[END_REF] implements some of the specific parameter computation but again uses the specific setup. Furthermore, the transmitter is included in the FPGA implementation, which simulates one communication partner. This makes it very easy to capture only a snipped of the communication because the FPGA well knows the point in time when a command is sent. However, simulating one communication partner and not using two complete NFC-enabled devices is not valid for interoperability testing. To get the specific snippet of a communication to analyze parameters such as described in [START_REF] Gebhart | Automatic analysis of 13.56 mhz reader command modulation pulses[END_REF][START_REF] Muehlmann | Automated analysis of iso/iec14443a interrogator command pulse shapes[END_REF][START_REF] Stark | How to guarantee phase-synchronicity in active load modulation for NFC and proximity[END_REF] a measurement system with smart trigger functionality is essential. High resolution but limited parameter. For some NFC communication relevant parameters, a standard oscilloscope without intelligent trigger functionality is sufficient. As shown in work [START_REF] Langer | A comprehensive concept and system for measurement and testing Near Field Communication devices[END_REF], the HF-field of the DUT can easily be measured without analyzing a command or a response. Therefore, such a test system is suitable and can be used to find some interoperability issues if they are related to the HF-field strength.

Conclusion and Future Work

In this paper, we present an NFC interoperability sniffer tool providing smart trigger functionalities to reduce test time during manual debug sessions. Furthermore, we provide a solution to capture NFC communication frames with very high sample rates. Before elaborating on the design of the sniffer tool we point to the importance of interoperability testing and the need for an additional device supporting the test engineer to analyze the signal of interest. In Section 2 we present the used hardware and explain implementation details. We evaluated the proof of concept and show how the different trigger features work. Furthermore, we show how the sniffer tool including the smart trigger functionalities connected with an external oscilloscope can be used to capture the communication snippet of interest for further interoperability analysis. The parallel implementation of the different features additionally increases the usability of the whole system also for other measurement purposes. Using the proposed smart NFC sniffer for high-precision measurements significantly reduces the time required to set up an oscilloscope and to capture the correct communication snippet. Our goal is to improve interoperability testing for NFC-enabled devices to on the one hand increase the user acceptance and user experience. On the other hand, interoperability testing should be included in the product development life cycle and into the certification process.

This system can be improved by implementing a real-time protocol decoder on the FPGA to support triggering on a specific command and not on a command number. Furthermore, we would like to support more different data rates and applications. Within the ANITAS project [START_REF]Österreichische Forschungsförderungsgesellschaft: Project homepage[END_REF] we will integrate this system to the automated NFC interoperability test system at CISC Semiconductor.. This will significantly reduce the time required during manual debug sessions.

FPGAFig. 1 :

 1 Fig. 1: Block Diagram of the FPGA Implementation

Fig. 2 :

 2 Fig. 2: Block Diagram of the FPGA Design

  Fig. 3: Evaluation Setup

Fig. 4 :

 4 Fig. 4: TypeB Communication with the different Trigger Features

Fig. 5 :

 5 Fig. 5: TypeB Communication showing Zoom 1

Fig. 6 :

 6 Fig. 6: TypeB Communication showing Zoom 2

Fig. 7 :

 7 Fig. 7: TypeB Communication showing Zoom 3

This work is part of the ANITAS project in cooperation with CISC Semiconductor, NXP Semiconductors, and the Institute of Technical Informatics at the Graz University of Technology. This project is partly founded by the Kärntner Wirtschaftsförderungsfonds and the Steirischen Wirtschaftsförderungssgesellschaft mbH under the FFG (Austrian Research Promotion Agency) grant number 864323.