Lucian Busoniu

Jihene Ben Rejeb

Ioana Lal

Irinel-Constantin Morarescu

Jamal Daafouz

Optimistic minimax search for noncooperative switched control with or without dwell time ⋆

Keywords: Switched systems, optimistic search, noncooperative optimal control, nonlinear systems

We consider adversarial problems in which two agents control two switching signals, the first agent aiming to maximize a discounted sum of rewards, and the second aiming to minimize it. Both signals may be subject to constraints on the dwell time after a switch. We search the tree of possible mode sequences with an algorithm called optimistic minimax search with dwell time (OMSd), showing that it obtains a solution close to the minimax-optimal one, and we characterize the rate at which the suboptimality goes to zero. The analysis is driven by a novel measure of problem complexity, and it is first given in the general dwell-time case, after which it is specialized to the unconstrained case. We exemplify the framework for networked control systems where the minimizer signal is a discrete time delay on the control channel, and we provide extensive simulations and a real-time experiment for nonlinear systems of this type.

Introduction

Switched systems toggle their dynamics among those in a set of dynamical modes [START_REF] Liberzon | Switching in Systems and Control., ser. Systems and Control: Foundations and Applications[END_REF][START_REF] Lin | Stability and stabilizability of switched linear systems: A survey of recent results[END_REF][START_REF] Zhu | Optimal control of switched hybrid systems: A brief survey[END_REF]. They model real-world systems subject to known or unknown abrupt parameter changes, e.g. in the automotive, aerospace, and energy management industries. This paper considers systems with two different switching signals, which occur in e.g. smart grids [START_REF] Saad | Game-theoretic methods for the smart grid: An overview of microgrid systems, demandside management, and smart grid communications[END_REF], networks [START_REF] Zheng | Stochastic dynamic network interdiction games[END_REF] or networked control systems, and have started to be considered in the literature e.g. by [START_REF] Bolzern | Design of stabilizing strategies for discrete-time dual switching linear systems[END_REF] where they were called dual switched systems. In our framework, the two signals are controlled by two adversarial agents that choose modes in turn, one of them aiming to maximize an infinite-horizon cumulative reward, and the other to minimize it. Such an infinite horizon is appropriate whenever decisions must be made repeatedly without a definite end of the control task. Either signal (or both) may be subject to dwell time constraints, so that after a switch it must be kept constant for at least an imposed number of steps. Mode dynamics are autonomous, general nonlinear, and the rewards must be bounded.

To find (an approximation of) a minimax-optimal solution, we will use optimistic methods, which combine ideas from global optimization, bandit theory for exploration in rein-⋆ We are grateful to Rémi Munos for his contribution to the initial unconstrained method [START_REF] Bus ¸oniu | An analysis of optimistic, best-first search for minimax sequential decision making[END_REF], and to Alexandru Codrean for his help with the experiments. This work was supported by a grant of the Romanian National Authority for Scientific Research, CNCS-UEFISCDI, project number PN-III-P1-1.1-TE-2016-0670, grant agreement no. 9/2018.

Email address: lucian@busoniu.net (Lucian Busoniu).

forcement learning, classical graph search and planning, and optimal control [START_REF]From bandits to Monte Carlo tree search: The optimistic principle applied to optimization and planning[END_REF]. It turns out that applying optimism in the adversarial setting naturally leads to a best-first variant [START_REF] Palay | The B* tree search algorithm -new results[END_REF] of B*, a classical minimax algorithm proposed for game tree search by [START_REF] Berliner | The B* search algorithm: A best first proof procedure[END_REF]. Since many other methods have been called "best-first search", and as we adapt the algorithm to handle infinite horizons and dwell times, we call it optimistic minimax search with dwell time (OMSd), keeping in mind its relation to B*. OMSd iteratively explores a tree representation of the possible sequences of max and min agent modes, by computing lower and upper bounds on the values of mode sequences passing through each node. At each iteration an optimistic leaf is expanded, by starting from the root and recursively traveling to an optimistic child, which maximizes the upper bound at max nodes or minimizes the lower bound at min nodes. OMSd is anytime: it can stop after any number of expansions, and returns the sequence of modes corresponding to a deepest expanded node. Thus it provides an adaptive-horizon solution. For closed-loop control, OMSd may be used in receding horizon.

By exploiting the optimistic framework, we develop nearoptimality and convergence rate guarantees for OMSdwhich to our best knowledge were missing from the literature on B* search, even in the unconstrained case. The analysis is done in the general case with dwell time constraints, and then specialized to the unconstrained case. The sequence returned by OMSd is near-optimal to the extent of the gap between the upper and lower bounds at the deepest expanded node, which can be computed a posteriori, once the algorithm stops. A priori, we characterize the rate at which the gap decreases with the computation invested Preprint submitted to Automatica (number of node expansions); the rate depends on the dwell time limits of the two signals and on a measure of problem complexity. The measure is quite challenging to define when dwell time constraints are imposed, because the structure of the tree obtained after eliminating nodes that violate the dwell time conditions is quite intricate. It specializes to an intuitive meaning in the unconstrained case: the average branching factor of the subtree explored. Interestingly, in a worst-case sense the constrained algorithm converges faster than the unconstrained one.

Because the min agent chooses its mode using knowledge of the max mode, OMSd solves a Stackelberg problem [START_REF] Breton | Sequential stackelberg equilibria in two-person games[END_REF][START_REF] Zheng | Stochastic dynamic network interdiction games[END_REF], with the max agent as the leader. In fact, the unconstrained framework can be applied to any such problem where the actions of the two agents are discrete or discretized, not just when they are mode switches. Stackelberg adversarial problems appear in network security [START_REF] Zhu | Stackelberg-game analysis of correlated attacks in cyber-physical systems[END_REF], pursuit-evasion [START_REF] Ehtamo | On applied nonlinear and bilevel programming for pursuit-evasion games[END_REF], and advertising [START_REF] He | Cooperative advertising and pricing in a dynamic stochastic supply chain: Feedback stackelberg strategies[END_REF], in addition to game playing [START_REF] Wang | Modifications of UCT and sequencelike simulations for Monte-Carlo Go[END_REF].

When the two mode choices are applied simultaneously, without the min agent knowing the max mode, a different type of problem ensues where the solution is a Nash equilibrium. In this case, we show that if the same algorithm is used, which still solves the problem as if it were a Stackelberg one, a relationship can nevertheless be established between the value of the sequence returned and the optimal Nash value, see also [START_REF] Leitmann | On generalized stackelberg strategies[END_REF].

In our experiments, the min mode is a discrete time delay on the control communication channel used to send the max mode, see [START_REF] Tzes | Development and experimental verification of a mobile client-centric networked controlled system[END_REF][START_REF] Hetel | Equivalence between the lyapunov-krasovskii functional approach for discrete delay systems and the stability conditions for switched systems[END_REF]. We study cases when an attacker hides behind the delay and controls it in a Stackelberg setting, with or without dwell time, and in a Nash setting solved as Stackelberg. Real-time results are provided for random delays, conservatively treated as an opponent.

In switched systems, OMSd is to our knowledge the first algorithm for optimal control under two switching signals; earlier work by [START_REF] Bolzern | Design of stabilizing strategies for discrete-time dual switching linear systems[END_REF] focused on stability, and applied to linear modes only. OMSd instead handles general nonlinear modes, and focuses on near-optimality guarantees -stability is a separate, difficult problem for the discounted costs that we use [START_REF] Postoyan | Stability analysis of discrete-time infinite-horizon optimal control with discounted cost[END_REF]. In [START_REF] Bus ¸oniu | Planning for optimal control and performance certification in nonlinear systems with controlled or uncontrolled switches[END_REF], we studied max-only switched problems; the minimax case here is more challenging, and specializes to the max-only case when the min agent is removed.

In planning, besides B* [START_REF] Berliner | The B* search algorithm: A best first proof procedure[END_REF][START_REF] Palay | The B* tree search algorithm -new results[END_REF] OMSd is related to other classical tree search methods such as alpha-beta pruning [START_REF] Knuth | An analysis of alpha-beta pruning[END_REF] or best-first search [START_REF] Korf | Best-first minimax search[END_REF]. OMSd belongs to the optimistic class, which provides algorithms for e.g. optimization [START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF], optimal control of discrete-action deterministic [START_REF] Hren | Optimistic planning of deterministic systems[END_REF] or stochastic systems [START_REF] Bus | Optimistic planning for Markov decision processes[END_REF]. A crucial feature of the analysis is the complexity measure, which is related to other measures in optimistic methods, such as the branching factor in [START_REF] Hren | Optimistic planning of deterministic systems[END_REF], or the near-optimality dimension in [START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF]. Different from these however, our measure works in minimax problems. In the unconstrained case, it specializes to a branching factor also related to the branching factor of alpha-beta pruning [START_REF] Knuth | An analysis of alpha-beta pruning[END_REF][START_REF] Pearl | The solution for the branching factor of the alpha-beta pruning algorithm and its optimality[END_REF]. However, OMSd is adaptive-depth (horizon) while alphabeta is fixed-depth. OMSd is closer to the adaptive-depth best-first method of [START_REF] Korf | Best-first minimax search[END_REF], which does not have an analysis and in fact may converge to suboptimal solutions [START_REF] Bus ¸oniu | An analysis of optimistic, best-first search for minimax sequential decision making[END_REF].

This paper integrates and extends the earlier work [START_REF] Bus ¸oniu | An analysis of optimistic, best-first search for minimax sequential decision making[END_REF] on unconstrained OMS, and [START_REF] Rejeb | Nearoptimal control of nonlinear switched systems with non-cooperative switching rules[END_REF] for dwell time constraints. Notable novel elements here include: (i) handling different dwell times for the two agents (in [START_REF] Rejeb | Nearoptimal control of nonlinear switched systems with non-cooperative switching rules[END_REF] they had to be the same, which is unrealistic); (ii) the study of the solution properties in the Nash case, which is important since often an agent does not have access to its opponent's action at the current step, (iii) a different and extensive experimental study, including a real-time illustration of the technique, and (iv) an integrated presentation of the framework that we show encompasses not just the unconstrained and dwelltime minimax cases, but also the single-agent case with or without dwell time [START_REF] Bus ¸oniu | Planning for optimal control and performance certification in nonlinear systems with controlled or uncontrolled switches[END_REF].

Next, Sec. In our algorithm and analysis, it will often be useful to treat max and min decisions uniformly. For that purpose, denote a generic (either max or min) mode by z ∈ Z := U ∪ W ; and define also index h that counts all decision steps, max or min. Thus, h advances twice as fast as k, which only increases with pairs of max-min decisions. For example, we have: z 0 = u 0 , z 1 = w 0 , z 2 = u 1 , z 3 = w 1 , . . . , z 2k = u k , z 2k+1 = w k , . . . . Denote an infinite sequence of modes by z ∞ = (z 0 , z 1 , z 2 , z 3 , . . . , z 2k , z 2k+1 , . . . ) = (u 0 , w 0 , u 1 , w 1 , . . . , u k , w k , . . . ) ∈ Z ∞ . A finite sequence of h modes is denoted z h = (z 0 , z 1 , . . . , z h-1 ), with z 0 the empty sequence by convention.

At each step h ∈ N, the system evolves according to:

x h+1 = f (x h , z h ) (1)
where x h ∈ X is the state, z h ∈ Z is the (max or min) mode, and f : X × Z → X are the (autonomous) mode dynamics. We prefer the notation f (x, z) instead of the more standard f z (x) as it avoids double subscripts. A reward (negative cost) ρ(x h , z h ) is assigned, where ρ : X × Z → R. Given an initial state x 0 , the infinite-horizon discounted value of sequence z ∞ is:

v(z ∞ ) := ∞ h=0 γ h ρ(x h , z h ) (2)
where γ ∈ (0, 1) is the discount factor. The goal is to achieve the minimax-optimal value, defined as:

v * := lim k→∞ max u0 min w0 • • • max u k min w k 2k-1 h=0 γ h ρ(x h , z h ) (3
) Intuitively, this value is the best achievable by the max agent under the worst-case assumption that the min agent always chooses the mode that is the most detrimental for performance. Very general technical conditions under which the solution exists can be found in [START_REF] Breton | Sequential stackelberg equilibria in two-person games[END_REF]. Note that the method we propose later will not reach this minimax value exactly or find a complete, infinite-horizon sequence; it will only get closer to the infinite-horizon value and sequence as the computation budget increases, by examining increasingly longer (but still finite) mode sequences.

Assumption 1 The rewards ρ(x, z) are in [0, 1] for all x ∈ X, z ∈ Z.
The main role of discounting and cost boundedness is to ensure that the value (2) is in [0, 1 1-γ ] for any sequence. This implies that for any finite sequence z h , l(z h ) := h-1 j=0 γ j ρ(x j , z j ) is a lower bound on the values of all sequences z ∞ starting with z h (with the convention that an empty sum is 0), and b(z

h ) := l(z h ) + γ h 1-γ is an up- per bound. Thus, v(z ∞ ) ∈ [l(z h ), b(z h )]. Let δ(h) = γ h 1-γ
denote the gap between the two bounds, an uncertainty on the values of sequences z ∞ starting with z h . These value bounds are essential to the derivation of our algorithm below. Thus, at the cost of some restrictiveness induced by the bounded rewards and by the subunitary discount factor, we obtain a method that works for general nonlinear dynamics and nonquadratic rewards.

Note moreover that many other works in control use discounting, e.g. [START_REF] Katsikopoulos | Markov decision processes with delays and asynchronous cost collection[END_REF]. Bounded rewards are typical in AI methods for optimal control, such as reinforcement learning [START_REF]Reinforcement Learning: State of the Art[END_REF]. One way to achieve boundedness is by saturating a possibly unbounded original function. This changes the optimal solution, but is often sufficient in practice. On the other hand, the system may have physical limitations that naturally lead to saturation limits and a corresponding bound.

Often, the max and min mode decisions are applied simultaneously, so the dynamics and rewards are:

y k+1 = g(y k , u k , w k ), r k+1 = r(y k , u k , w k ) (4)
where y k ∈ Y is the state signal of the simultaneousdecision problem, while g and r denote the dynamics and reward function of this problem (and r k is a particular reward at step k). The infinite-horizon value to optimize is ∞ k=0 β k r(y k , u k , w k ), with β ∈ (0, 1) a new discount factor. Since the system can be in any combination of modes u and w, the total number of modes is N u • N w .

We will represent this problem in the turn-based form (1)- [START_REF] Bolzern | Design of stabilizing strategies for discrete-time dual switching linear systems[END_REF]. To this end, we define the turn-based state vector

x ∈ Y × {U ∪ {s}} so that in addition to the state of the simultaneous-decision problem, it also contains an extra state variable. This variable takes special value s / ∈ U at max steps, and at min steps remembers the latest max mode. Recalling that index h advances twice as fast as k, we have formally that at (even, max) steps h = 2k,

x h = x 2k = [y ⊤ k , s] ⊤ , while at (odd, min) steps h = 2k + 1, x h = x 2k+1 = [y ⊤ k , u k ] ⊤ .
Using turn-based state x, g is represented by the following turn-based dynamics f in (1):

f (x h , z h ) = [y ⊤ k , u k ] ⊤ if h = 2k [g(y k , u k , w k ) ⊤ , s] ⊤ if h = 2k + 1
Rewards are similarly represented:

ρ(x h , z h ) = 0 if h = 2k r(y k , u k , w k ) if h = 2k + 1
Note that f and r are time-invariant, so they cannot directly check whether h is even; however, this can be determined by examining the last, special state variable, which equals s at even steps. We have

∞ h=0 γ h ρ(x h , z h ) = γ ∞ k=0 γ 2k r(y k , u k , w k ), so to optimize the intended ob- jective function (2) with discount factor β, we take γ = √ β.
While here we focus on switched systems, the framework can in fact be applied to any adversarial decision-making problem where the actions of the two agents are discrete or discretized. One reason for which we prefer the turn-based formalism (1)-( 3) is that in this general context, it covers additional problems like two-player games.

Dwell time constraints

In switched systems, modes must often be kept constant over a minimum dwell time, in order to guarantee fundamental stability or performance properties, to obey actuation constraints, etc. In particular, switching signals u and w have minimum dwell-time limits d u and d w . For the max agent the dwell-time is defined as the number of max decision steps during which the mode u remains constant after a change, and the condition requires that all dwell times along the sequence are at least as large as d u , see Fig. 1 for an example. The situation is similar for the min signal w. Dwell times therefore only increase once every two steps h (corresponding to one step k). Taking a limit equal to 1 is equivalent to not imposing a dwell-time condition for that signal, so the unconstrained problem is recovered when

d u = d w = 1.
The objective (3) changes to reflect the constrained nature of the switching sequences. Denote by U (z h ) and W (z h ) respectively the set of all max and min modes at step h that satisfy the dwell-time constraints given prior modes z h . E.g., U (z h ) = U when z h already satisfies the max dwell time condition at h, and otherwise U (z h ) is equal to the last max mode along sequence z h . Then, the constrained minimax

k = 1 (h = 2k = 2)
, the max agent has switched from mode 1 to mode 2; since its dwell time limit is 2, it must wait until at least

k = 1 + 2 = 3 (equivalently, until h = 6) before it is allowed to select a new mode, different from 2.
Here, it selects mode 3.

In contrast, had the problem been unconstrained, the max mode could have already been changed at k = 2.

value to be achieved is:

v * := lim k→∞ max u0∈U (z0) min w0∈W (z1) • • • • • • max u k ∈U (z 2k ) min w k ∈W (z 2k+1 ) 2k h=0 γ h ρ(x h , z h ) (5)

Nash problem

In both the unconstrained and constrained problems above, when it chooses w k the min agent knows and can react to the max action u k . This is a Stackelberg, leader-follower setting with the max agent as the leader, and it useful in many practical problems such as network security [START_REF] Zhu | Stackelberg-game analysis of correlated attacks in cyber-physical systems[END_REF][START_REF] Zheng | Stochastic dynamic network interdiction games[END_REF], pursuitevasion problems [START_REF] Ehtamo | On applied nonlinear and bilevel programming for pursuit-evasion games[END_REF], or advertising [START_REF] He | Cooperative advertising and pricing in a dynamic stochastic supply chain: Feedback stackelberg strategies[END_REF]. This setting was implicitly assumed throughout [START_REF] Bus ¸oniu | An analysis of optimistic, best-first search for minimax sequential decision making[END_REF][START_REF] Rejeb | Nearoptimal control of nonlinear switched systems with non-cooperative switching rules[END_REF]. However, if the two agents act simultaneously (4) and the min agent does not have access to u k at step k, then the Stackelberg solution concept is no longer appropriate, and the Nash equilibrium is usually employed (also called a saddle-point solution in the adversarial setting here). Nevertheless, as we show next, the problem can still be solved as if it were a Stackelberg one, which under certain conditions provides a bound on the Nash value -see also [START_REF] Leitmann | On generalized stackelberg strategies[END_REF]. This bound will later be coupled with the near-optimality guarantees of our algorithm to relate the sequence it returns with the Nash value. For simplicity, we stick to unconstrained sequences in the Nash setting.

First, it will help to make the infinite-horizon Stackelberg solution more explicit. For t ≥ 0 define the sequence of value functions

v t : Y → R, ṽt : Y × U × W → R: ṽt (y, u, w) = r(y, u, w) + βv t-1 (g(y, u, w)) v t (y) = ṽt (y, u t (y), w t (y, u t (y))) (6)
starting from the initial function v 0 (y) = 0. Function equalities and inequalities hold elementwise. Here, w t (y, u) ∈ arg min w ṽt (y, u, w) is a reaction function of the min agent to max decisions u; if there are multiple minimizer actions, a selection rule among them must be imposed. Moreover, u t (y) ∈ arg max w ṽt (y, u, w t (y, u)) is a Stackelberg-optimal decision of the max agent given the reaction function w t . Then, the infinite-horizon Stackelberg value from initial state y is v * (y) = lim t→∞ v t (y), and is the same as (3).

In contrast, a pure (deterministic) Nash solution is defined as follows, using

v N t : Y → R, ṽN t : Y × U × W → R: ṽN t (y, u, w) = r(y, u, w) + βv N t-1 (g(y, u, w)) v N t (y) = ṽN t (y, u N t (y), w N t (y)) (7)
where v N 0 (y) = 0 and u N t (y), w N t (y) is a Nash equilibrium at stage t in state y, i.e. a pair of decisions such that ṽN t (y, u,

w N t (y)) ≥ ṽN t (y, u N t (y), w N t (y)) ≥ ṽN t (y, u N t (y), w), ∀u, w. The infinite-horizon Nash value is then v * N (y) = lim t→∞ v N t (y).
Note that this definition requires the existence of a deterministic Nash equilibrium at each t, y, and if there are several such equilibria, a selection rule must be imposed to have a well-defined sequence.

Proposition 2 The infinite-horizon Stackelberg value is larger than the Nash one

: v * ≥ v * N .
Proof: We prove the statement by induction, starting from

v 0 = v N 0 = 0. Take t ≥ 1 and assume v t-1 ≥ v N t-1 .
Then, for any y:

v t (y) = ṽt (y, u t (y), w t (y, u t (y))) ≥ ṽt (y, u N t (y), w t (y, u N t (y))) ≥ ṽN t (y, u N t (y), w t (y, u N t (y))) ≥ ṽN t (y, u N t (y), w N t (y)) = v N t (y)
where the first inequality is true because the Stackelberg max decision u t (y) maximizes ṽt (y, u, w t (y, u)) over u; the second because ṽt-1 (y, x, u) ≥ ṽN t-1 (y, u, w), ∀y, u, w, which immediately follows from v t-1 (y) ≥ v N t-1 (y); and the third inequality holds because the Nash min decision w N t (y) minimizes ṽN t (y, u N t (y), w) over w.

Algorithm

We will present the optimistic minimax search (OMSd) algorithm in the dwell-time case from Sec. 2.2, which will reduce naturally to the unconstrained problem of Sec. 2.1 when

d u = d w = 1.
OMSd explores a tree representation of the possible sequences of max and min modes. It starts with a root node corresponding to the empty sequence, and iteratively expands n nodes taking into account dwell-time conditions. to max modes, and similarly for min decision nodes. Each arc is labeled by the mode taken at the parent node to reach the child. Specifically, at max nodes, if the max dwell-time is at least d u then N u children nodes are created, one for every max mode; otherwise, i.e. if the max dwell-time condition is not satisfied, only the child that keeps the mode constant is added. Similarly, N w children nodes are added at a min node if its min dwell-time is at least d w , and only the constant-mode child is added otherwise. For example, the node labeled 1/3 in the figure has max dwell time 1 because the max mode taken to reach it, 'b', is different from the previous max mode 'a' taken two levels higher (at the root), so a max switch just occurred. These two different modes are highlighted by gray arcs. Note that this particular node is not immediately affected by the non-satisfaction of the max dwell time, since it is a min decision node; indeed, both its children are created since the min dwell time is still 3, and the constraint only has an effect at the next depth, where the only allowed max mode is 'b'. Fig. 2 also illustrates some constrained min node expansions, from depth 5 to 6.

Each node at some depth h is reached via a unique path through the tree, and so is uniquely associated to the sequence of modes z h on this path. We denote by d u (z h ) and d w (z h ) the current max and min dwell-times of z h . We will work interchangeably with sequences and nodes.

Let T denote the current tree, L(T ) the leaf nodes of this tree, and C(z) the children of node z, all satisfying the dwelltime constraints (so C(z) is sometimes a singleton). The algorithm computes lower and upper bounds L(z) and B(z) for each node. The bounds are initialized with l and b at the leaves and propagated upwards in the tree:

L(z) =    l(z), if z ∈ L(T ) max z ′ ∈C(z) L(z ′ ), if z max node, z / ∈ L(T ) min z ′ ∈C(z) L(z ′ ), if z min node, z / ∈ L(T ) B(z) =    b(z), if z ∈ L(T ) max z ′ ∈C(z) B(z ′ ), if z max node, z / ∈ L(T ) min z ′ ∈C(z) B(z ′ ), if z min node, z / ∈ L(T ) (8)
To better understand, consider a subtree developed by the algorithm after 4 node expansions, shown in Fig. 3 (a subtree of the tree in Fig. 2). This figure shows the bounds associated with each node, initialized to illustrative values at the leaves z ← z 0 4:

while z / ∈ L(T ) do 5: z ← arg max z ′ ∈C(z) B(z ′ ), if z max node arg min z ′ ∈C(z) L(z ′ ), if z min node 6: z(t) ← z 7:
expand z(t), by adding its children to T : compute bounds for all z ∈ T with (8) Output: ẑ := arg max z(t),t=1,...,n h(z), l(ẑ), b(ẑ) and propagated with [START_REF] Bus ¸oniu | An analysis of optimistic, best-first search for minimax sequential decision making[END_REF]. For example, since the root z 0 is a max node, its lower bound L(z 0 ) = 0.75 is found as the maximum of the two children's bounds, 0 and 0.75; and similarly for the upper bound B(z 0 ).

To choose the leaf to expand at each iteration, OMSd starts from the root and constructs a path by iteratively selecting an optimistic child of the current node, where optimistic means that the child is one with the largest upper bound at max nodes, and one with the smallest lower bound at min nodes. For instance, in Fig. 3, starting from the root first the right child is selected, because the root is a max node and the right child has the largest upper bound, namely 1.5; then at this next (min) node, its left child is selected, since it has the smallest lower bound, 0.75, and so on along the thick path until a leaf is reached, which is then expanded.

After n node expansions, the algorithm stops and returns the sequence ẑ and the bounds of a deepest expanded node. Alg. 1 summarizes OMSd, where (•, •) denotes sequence concatenation and h(•) yields the depth of a sequence.

When d u = d w = 1, since any mode is kept for at least one step, the dwell time of any node is at least 1, so the inner "else" branches never get activated, children for all modes are always created, and the algorithm solves the unconstrained problem of Sec. 2.1. The algorithm is then an infinite-horizon extension of B* search [START_REF] Berliner | The B* search algorithm: A best first proof procedure[END_REF].

OMSd will often be used to find max modes to apply. The algorithm should then typically applied in receding horizon, calling it with the current state at max decision steps where the dwell time condition is satisfied. If the condition is not satisfied, then the max mode must be kept constant anyway so it is not useful to run OMSd. To exemplify, assume that the minimax switching sequence in Figure 1 is obtained by such a closed-loop application of OMSd. The algorithm is first called at h = k = 0, resulting in the first max mode, which is applied, and the min agent generates its own mode. OMSd is next called at h = 2, corresponding to k = 1, at which time it generates a different mode, and again the min agent responds. Now, since a max switch has occurred, the max mode must be kept constant for the next step, and OMSd is only called again at h = 6, or k = 3; and so on. Of course, when there is no dwell time constraint the algorithm must be called at each step. Min switches must also obey their own dwell time, and OMSd takes advantage of this information by skipping sequences that do not satisfy the min constraint. Note that the min agent can in general use any algorithm, including OMSd.

Analysis

Constrained case

Like the algorithm itself, the analysis will first be given in the case with dwell time constraints, and then specialized to the unconstrained case. We begin by establishing an a posteriori near-optimality bound with respect to the minimax value. Then, a complexity measure of the problem and a corresponding convergence rate of OMSd are established. In [START_REF] Rejeb | Nearoptimal control of nonlinear switched systems with non-cooperative switching rules[END_REF] the two dwell times d u , d w had to be equal for the analysis to work. Since this is unrealistic in most cases, here we extend the analysis to different dwell times, which impacts everything from the complexity measure onward.

Define for any node z h of finite depth h the minimax value v(z h ) among infinite sequences starting with z h and obeying the dwell time constraints. Specifically:

v(z h ) = h-1 j=0 γ j ρ(x j , z j )+            max z h ∈U (z h ) min z h+1 ∈W (z h+1 ) • • • ∞ j=h γ j ρ(x h , z h ) if z h max node min z h ∈W (z h ) max z h+1 ∈U (z h+1 ) • • • ∞ j=h γ j ρ(x h , z h ) if z h min node (9)
The next Lemma characterizes the subset of nodes expanded by the algorithm, which is in general not the full tree.

Lemma 3 (Lemma 3 of [24]) At depth h in the tree, OMSd only expands nodes in the set:

T * h := z h |v * -v(z p )| ≤ δ(h), ∀z p on path from root to z h (10)
An important feature of T * is the nonlocal character of the inequality in [START_REF] He | Cooperative advertising and pricing in a dynamic stochastic supply chain: Feedback stackelberg strategies[END_REF], which must hold for any parent and not just the expanded node.

We give now an a posteriori near-optimality bound, which can be computed after the algorithm stops.

Theorem 4 (Theorem 4 of [24]

) Let h * be the largest depth of any expanded node. Then,

|v * -v(ẑ)| ≤ δ(h * ) and v * ∈ [L(z 0 ), B(z 0 )].
The analysis given so far was known from [START_REF] Rejeb | Nearoptimal control of nonlinear switched systems with non-cooperative switching rules[END_REF]. However, since unlike in [START_REF] Rejeb | Nearoptimal control of nonlinear switched systems with non-cooperative switching rules[END_REF], here d u may be different from d w , the upcoming analysis must be updated to take this into account.

To that end, let d = min{d u , d w } and N = max{N u , N w }.

To establish an a priori bound, we must first characterize the size of the expanded subtree T * = h≥0 T * h via a complexity measure κ that evaluates the difficulty of the search problem. In the sequel, |•| denotes set cardinality.

Definition 5 Let κ be a number so that ∃C > 0,

|T * h | ≤ Cκ h/d , ∀h ≥ 0.
Note that κ is similar with other complexity measures used in optimistic optimization and planning [START_REF]From bandits to Monte Carlo tree search: The optimistic principle applied to optimization and planning[END_REF], such as the branching factor in [START_REF] Hren | Optimistic planning of deterministic systems[END_REF], the near-optimality dimension in [START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF], and the near-optimality exponent in [START_REF] Bus | Optimistic planning for Markov decision processes[END_REF]. Before the final bound, we study the range of κ, starting with the largest value (the most difficult problem).

Proposition 6 A finite κ always exists, and κ ≤ dN .

Proof: It suffices to consider the case when the full tree T is expanded, since then T * = T , which leads to the largest number of nodes in T * h and hence the largest κ. This occurs in a problem where all the rewards are identical. Any sequence is optimal in this case and the algorithm must explore the entire tree uniformly.

First, denote by T the tree of sequences with equal dwell times for both max and min, d ′ u = d ′ w = d. We have T ⊆ T . To prove this, consider any node z ∈ T . Since z satisfies the original dwell time constraint,

d u (z) ≥ d u ≥ d = d ′
u , and z also satisfies the looser constraint from T . A similar reasoning holds for the min agent, so z ∈ T .

Next, define the matrix M h ∈ R d×d , the elements of which count nodes with various max and min dwell times at depth h in T :

M h,ii ′ =        #(d u = i, d w = i ′ ), if i < d, i ′ < d #(d u ≥ i, d w = i ′ ), if i = d, i ′ < d #(d u = i, d w ≥ i ′ ), if i < d, i ′ = d #(d u ≥ i, d w ≥ i ′ ), if i = d, i ′ = d
where #(•) is shorthand for "the number of nodes at h satisfying condition •". So, the non-terminal rows i < d count the number of nodes with a max dwell-time of exactly i, while the last row is special: it counts the nodes with a max dwell-time of d or larger. The situation is similar for the columns, which correspond to the min dwell time. Then:

|T h | = d i=1 d i ′ =1 M h,ii ′
Matrix M h satisfies at all depths of the form 2jd, j ∈ N:

M 2jd ≤         (dN ) 2j (N -1) ... (dN ) 2j (N -1) (dN ) 2j (N -1) . . . . . . . . . . . . . . . (dN ) 2j (N -1) (dN ) 2j (N -1) ... (dN ) 2j (N -1) (dN ) 2j         =: M 2jd (11
) with matrix inequalities holding elementwise. The proof of this property is very technical and we do not include it here, instead referring the reader to the supplementary material at: busoniu.net/files/papers/swminmax_ suppl.pdf. Take j = h 2d . We have

i,i ′ M h,ii ′ ≤ i,i ′ M 2jd,ii ′ ,
as the number of explored nodes increases with the depth, and on the other hand M 2jd,ii ′ ≤ M 2jd,ii ′ from [START_REF] Hetel | Equivalence between the lyapunov-krasovskii functional approach for discrete delay systems and the stability conditions for switched systems[END_REF]. Then:

|T h | ≤ d i=1 d i ′ =1 (dN ) 2j (N -1) ≤ d 3 N (dN ) h/d (N -1) = C(dN ) h d with C = d 3 N (N -1), and since T * h = T h ⊆ T h , finally κ ≤ dN .
Regarding the smallest value of κ, it is trivially 1, since there must be at least one node in T * h : the one belonging to an optimal sequence.

Example 7 A problem with κ = 1. Consider the problem represented by the tree in Fig. 4. For each max node along the path on the left of the tree, one child has reward 1 and all other children have reward 0, and the same is true of their complete subtrees. The situation is reversed at min nodes. Thus, the leftmost path is minimax-optimal, with value v * = γ 0 + γ 2 + . . . = 1 1-γ 2 . This path is constructed such that it obeys the dwell time constraints. To study T * , consider an arbitrary node z h+g at depth h + g that is not on the optimal path, but does belong to the subtree of some max node z h which is on this path at an even depth h. Two examples of such nodes are shown by 'x' symbols in the figure. Then, the value of

z h+g is v(z h+g ) = γ 0 + γ 2 + . . . + γ h-2 = 1-γ h 1-γ 2 . Since δ(h + g) = γ g+h
1-γ , node z h+g can be excluded when:

|v * -v(z h+g )| > γ g+h 1-γ , i.e. when γ h 1-γ 2 > γ g+h 1-γ , for which it suffices if g > log (1-γ 2 )/(1-γ) log 1/γ
, a positive constant which we call G. Similarly, take now a node at depth h + g on a nonoptimal subtree of a min node at an odd h, as exemplified by a '+' in the figure . The value of such a node is

γ 0 + γ 2 + . . . + γ h-1 + γ h + γ h+1 + γ h+2 + . . . = γ 0 + γ 2 + . . . + γ h-1 + γ h+1 + γ h+3 + . . . + γ h + γ h+2 + . . . = 1+γ h 1-γ 2
where the intermediate step separated odd and even powers of γ at depth h and larger. Solving the exclusion condition results in the same lower bound G on g as for max nodes.

At some arbitrary depth h ′ the set T * h ′ contains at most 1+N +N 2 +. . .+N G =: C children coming from optimal nodes at various depths h < h ′ , which cannot be excluded via the conditions above. Thus, T * h ′ ≤ C and κ = 1. Finally, we give the a priori near-optimality result, in which the rates have the same mathematical form as in Theorem 7 of [START_REF] Rejeb | Nearoptimal control of nonlinear switched systems with non-cooperative switching rules[END_REF] (so that the proof there can be applied), but due to the generalized Definition 5 now also work for the case of different dwell times.

Theorem 8 Given budget n, we have:

|v * -v(ẑ)| ≤ δ(h * ) ≤ O(n -d log 1/γ log κ ) if κ > 1 O(γ n/C ) if κ = 1 ( 12
)
where C is the constant from Definition 5.

Therefore, when κ is smaller (i.e. the problem is simpler), the algorithm converges faster with n, since the negative exponent of n is larger in magnitude. In particular, κ = 1 leads to exponential convergence in n. Furthermore, stronger dwell time conditions, represented by larger d, also increase the exponent, so the algorithm is also faster when the dwell time limits are larger, which makes sense since there are fewer solutions to consider. In the worst case, κ = dN and near-optimality is O(n d log 1/γ log dN ).

Unconstrained and single-agent cases

We show here that the analysis above specializes to the unconstrained setting, recovering (with minor conservatism) all the results from [START_REF] Bus ¸oniu | An analysis of optimistic, best-first search for minimax sequential decision making[END_REF]. The analysis further encompasses the single-agent case with [START_REF] Bus ¸oniu | Planning for optimal control and performance certification in nonlinear systems with controlled or uncontrolled switches[END_REF] or without dwell time [START_REF] Hren | Optimistic planning of deterministic systems[END_REF],

showing that the algorithm we provide here is a general tool for decision-making in single-agent or adversarial problems.

Consider first the unconstrained case, i.e. when d u = d w = d = 1. The entire analysis above holds as stated, however it simplifies in interesting ways starting from Definition 5.

This formula now only requires |T * h | ≤ Cκ h , so κ has an intuitive meaning in this case: it is the asymptotic branching factor of the near-optimal tree, i.e. the average number of children of each node on this tree, for large depths h. The a priori bound in the case κ = 1 remains the same, whereas it becomes O(n -log 1/γ log κ ) for κ > 1. The analysis from [START_REF] Bus ¸oniu | An analysis of optimistic, best-first search for minimax sequential decision making[END_REF] has been recovered. The range of κ is however [1, N ], as opposed to [1, √ N u N w ] in [START_REF] Bus ¸oniu | An analysis of optimistic, best-first search for minimax sequential decision making[END_REF], so some conservatism is introduced.

Introducing dwell-time constraints may either reduce or increase problem complexity, depending on whether they remove near-optimal solutions that would be difficult for the algorithm to find, leaving it with simpler ones, or the other way around. An explicit relation can be found for the case when the full trees are explored. Then, the convergence rates are O(n -log 1/γ log N ) for the unconstrained problem, and O(n -d log 1/γ log dN ) for the constrained one. We have d log 1/γ log dN ≥ log 1/γ log N for d ≥ 2, so the constrained algorithm is faster.

In addition to generalizing the unconstrained minimax analysis to the dwell-time case, the analysis above also generalizes the single-agent (max-only) analysis with dwell time from [START_REF] Bus ¸oniu | Planning for optimal control and performance certification in nonlinear systems with controlled or uncontrolled switches[END_REF] to the minimax setting. In particular, by taking a singleton set of min modes to effectively remove the min agent, we get the bound O(n -du log 1/γ log κ ) from [START_REF] Bus ¸oniu | Planning for optimal control and performance certification in nonlinear systems with controlled or uncontrolled switches[END_REF]. Furthermore, by removing the dwell-time constraint from this single-agent problem (or equivalently, the min agent from the unconstrained minimax problem), we obtain the algorithm and guarantees for optimistic planning for deterministic systems in [START_REF] Hren | Optimistic planning of deterministic systems[END_REF], which we also applied in [START_REF] Bus ¸oniu | Planning for optimal control and performance certification in nonlinear systems with controlled or uncontrolled switches[END_REF] to max-only unconstrained switches. These relationships are graphically represented in Fig. 5.

agents, dwell time (this paper)

1 agent, dwell time 2 agents, no dwell time 1 agent, no dwell time [START_REF] Bus ¸oniu | An analysis of optimistic, best-first search for minimax sequential decision making[END_REF] [5]

[12] Fig. 5. Relationships between different planning settings and their analysis. The arrows point from the more general result to the one.

Remark 1 Let us consider what happens when

OMSd is applied to the Nash problem from Sec. 2.3. We study the return l( z) of the finite-length sequence found by OMSd. The proof of Theorem 4 of [START_REF] Rejeb | Nearoptimal control of nonlinear switched systems with non-cooperative switching rules[END_REF] implies that v * -l( z) ≤ δ(h( z)) = δ(h * ). Coupling this with v * ≥ v * N from Proposition 2, we have finally that l( z) ≥ v * N -δ(h * ), i.e. if the sequence returned were applied by the two agents, the return obtained would not be far from the Nash value.

Experimental evaluation

Our framework can address a wide range of noncooperative switched problems. Here, we consider networked control systems where the controller sends the chosen max modes to the system over a communication network affected by delays that are multiples of the sampling time. The delay is either controlled by an attacker who changes it so as to hinder performance, or otherwise it is random. In both cases we model the delay as a min switching signal, inspired by [START_REF] Hetel | Equivalence between the lyapunov-krasovskii functional approach for discrete delay systems and the stability conditions for switched systems[END_REF] and [START_REF] Tzes | Development and experimental verification of a mobile client-centric networked controlled system[END_REF].

The attack setting is close to network security games [START_REF] Zhu | Stackelberg-game analysis of correlated attacks in cyber-physical systems[END_REF][START_REF] Zheng | Stochastic dynamic network interdiction games[END_REF], and in particular to [START_REF] Zhu | Stackelberg-game analysis of correlated attacks in cyber-physical systems[END_REF] where the attacker can interfere with values sent along the control and measurement channels; here, the attacker attempts instead to mask its presence behind an innocuous delay signal. We give three examples in this setting. In the first example (Sec. 5.1), the max and min switching signals are unconstrained, leading to a problem of the type in Sec. 2.1. In the second example (Sec. 5.2), the delay signal must obey a minimum dwell time, as in Sec. 2.2. In the third example (Sec. 5.3), the min agent does not see the max mode before choosing the delay, illustrating the Nash problem of Sec. 2.3. Note that throughout Sec. 5.1-5.3, the delay agent explicitly acts to as to hinder the control agent, so the problem is truly noncooperative. Finally, Sec. 5.4 illustrates the method in real-time control, for a random delay signal that is still conservatively modeled as a noncooperative agent.

Before showing the results, we explain how the delay is modeled. Consider the system:

ỹk+1 = g(ỹ k , u k-w k ), ∀k > 0 (13)
where ỹk ∈ R p represents the system state at time k ∈ Z + , u k-w k is the controlled mode, and w k is the delay (number of steps by which u is delayed) at k, which takes integer values in {0, 1, . . . , m}, m ≥ 0, so N w = m + 1. A reward r(ỹ k , u k-w k ) is used that takes values in [0, 1]; note that the reward uses the delayed input, which means that it is generated at the system side. We will transform the problem in the minimax form (4), by defining dynamics g(y, u, w) and rewards r(y, u, w) that work with augmented state y. This state is, at step k:

y k = [y 0 k ⊤ , y 1 k , y 2 k , . . . , y m k ] ⊤ := [ỹ ⊤ k , u k-1 , u k-2 , . . . , u k-m ] ⊤
Then, the augmented dynamics g that represent [START_REF] Katsikopoulos | Markov decision processes with delays and asynchronous cost collection[END_REF] are:

y k+1 = g(y k , u k , w k ) :=[ỹ ⊤ k+1 , u k , u k-1 , . . . , u k-m+1 ] ⊤ = [ỹ ⊤ k+1 , u k , y 1 k , . . . , y m-1 k ] ⊤
where the underlying state ỹk+1 is computed as follows:

ỹk+1 = g(ỹ k , u k ) = g(y 0 k , u k ) if w k = 0 g(ỹ k , u k-w k ) = g(y 0 k , y w k k ) if w k > 0
The augmented reward function r that represents r is:

r(y k , u k , w k ) := r(ỹ k , u k ) = r(y 0 k , u k ) if w k = 0 r(ỹ k , u k-w k ) = r(y 0 k , y w k k ) if w k > 0
This framework is general enough to allow any nonlinear dynamics g. In all the simulations (Sec. 5.1-5.3), we apply it to an inverted pendulum driven by a DC motor, with two states: angle α and angular velocity α, and a voltage input ũ. The continuous-time dynamics are given e.g. in [START_REF] Bus ¸oniu | A review of optimistic planning in Markov decision processes[END_REF], and are discretized via numerical integration with T s = 0.05 s to obtain g. The goal is to stabilize the mass pointing upwards (corresponding to α = 0), and the maximum voltage (3 V) is insufficient from some initial states to bring the mass up in one go; instead it must first be swung back and forth to accumulate energy. To perform these swing-ups, the control therefore requires large planning horizons, and adding time delays further increases the difficulty.

The reward is taken quadratic, -(5α 2 + 0.1 α2 + ũ2 ), and normalized to [0, 1] using the knowledge that ũ ∈ [-3, 3] V, as well as the state bounds α ∈ [-π, π] rad, α ∈ [-15π, 15π] rad/s enforced by saturation. The reward can be written as a function r or r. We take discount factor β = 0.97, corresponding to γ = √ 0.97. 1 There are N u = 3 controlled modes: modes 1 and 3 correspond to the maximum-magnitude voltage levels, namely -3 and 3 V, while mode 2 is a stabilizing, linear state feedback ũ = K • [α, α] ⊤ saturated to ±1.5 V. The gains K are designed with discounted LQR on the linearized dynamics around zero, see Ch. 3 of [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]. Note that this lower-level feedback is on the system side, so it is not affected by delays. It only stabilizes the system from the neighborhood of the target equilibrium, and cannot perform the (nonlinear) swingup. The delay is either 0 or 1 steps, leading to N w = 2. It should also be noted that the implementation of OMSd exploits the knowledge that rewards are 0 at max steps to compute tighter bounds than the general formulas after Assumption 1; the analysis remains conservatively valid.

Results in the unconstrained case

In the first experiment, the control and delay signals do not have dwell time constraints (d u = d w = 1). The max agent applies OMSd in receding horizon as explained at the end of Sec. 3. The min agent could apply any algorithm, but here it uses OMSd, also in receding horizon. For each agent, a small, medium, and large budget are tested; the min agent values are smaller overall as it is intuitively easier to hinder via delays than to solve the task. Specifically, the budget n of the max agent takes values 3000, 6000, 9000, and for the min agent n w = 100, 500, 1000. For each combination a 100-step long controlled trajectory is executed, and Fig. 6 reports the discounted returns obtained. Performance generally decreases for larger n w , as expected, since the min agent becomes better at hindering the control. Performance is better for n = 6000 than for 9000; this sometimes occurs for planning algorithms, since small budgets (short horizons) can lead by luck to good long-term solutions.

1 A numerical study in the unconstrained case of Sec. 5.1 shows that taking β (or equivalently γ) much smaller or larger than these values leads to lower performance in terms of the total, undiscounted rewards. Fig. 7 shows a representative trajectory, for n = 9000 and n w = 500, selected to have medium performance. The swingup and stabilization are achieved, although the initial part with negative angles can be shortened to improve performance, by applying a more the maximum-magnitude mode 3 instead of the lower-magnitude mode 2 (which the algorithm identifies e.g. for n = 6000).

Results with dwell-time constraints

Next, the delay is restricted to satisfy a minimum dwell-time d w . Such a condition arises e.g. when the attacker wishes to imitate a delay signal with a bounded rate of change. Fig. 8 shows the dependence of the return on d w for n = 3000, n w = 500. Performance generally increases as the delay signal must obey stricter constraints, although there is a small decrease from 2 to 3, which may be due e.g. to a lucky solution of the min agent.

Results in the Nash problem

So far the attacker (min agent) could observe the max mode before it decided on the delay. In this section, we assume that it cannot, which leads to a Nash setting as in Sec. 2.3. The max agent can simply continue applying the Stackelberg algorithm, in which case Proposition 2 and the Remark of Sec. 4 hold. To allow a symmetrical reasoning to hold for the min agent, it can still apply OMSd but it has to solve a "reversed" Stackelberg problem where it is the leader and the max agent can react to its mode choice. The easiest way to understand this problem is to swap the two agents in problem (4), making the min agent the max one, with swapped signals u ′ = w and w ′ = u, the same dynamics g ′ (x, u ′ , w ′ ) = g(x, u, w), and a reversed reward function r ′ (x, u ′ , w ′ ) = 1 -r(x, u, w). Then, (4) can be solved as usual, with OMSd from the perspective of the new max agent u ′ . Once both u and w = u ′ have been decided, they are applied and the procedure is iterated in receding horizon. Fig. 9 shows the returns obtained for the same budgets as in Fig. 6. The same trend of good performance with n = 6000 is observed, although now n = 9000 also works well; the effect of n w is less clear than before.

Note that in [START_REF] Rejeb | Nearoptimal control of nonlinear switched systems with non-cooperative switching rules[END_REF], we provided simulation results for the case when the delay is an uncontrolled random signal. This illustrates that our method can be applied for robust control, where the disturbance (here, the delay) is conservatively handled as a smart min agent. We not repeat these results here, moving on instead to a real-time example where the delay is also random.

Real-time results for the rotational pendulum

We finally report a real-time control experiment, on a different, rotational pendulum, in which the pendulum link is indirectly driven via a horizontal link actuated by the motor. The states are the pendulum and horizontal joint angles, α and θ, and their angular velocities. The controlled modes u are, in order: the minimum voltage -6 V, a stabilizing controller saturated to ±3 V, computed with discounted LQR as for the simple pendulum above, and the maximum voltage 6 V. The sampling time is 0.04 s, and the unnormalized, quadratic reward function is ρ(x, u) = -15α 2 -0.05( α2 +θ 2 + θ2 + ũ2 ), with ũ the voltage. The delay is still 0 or 1 steps, and the discount factor β = 0.95.

The pendulum is initially in the stable downwards position, and the first control is computed as usual. Afterwards, the procedure must be changed for real-time control. We cannot wait until sampling instant k 1 to run the planner at x k+1 , since the execution time would be too long. Instead, planning is run for step k + 1 already during sampling interval k. However, the delay w k only becomes known at sampling instant k + 1, once we get information about it along the feedback path. Thus during sampling interval k we must develop minimax trees from the predicted outcome states of all possible delays. Instead of using a prespecified budget, the sampling interval is divided equally among the trees developed, with a safety margin to ensure the algorithm finishes in time, and OMSd is run for each outcome state until it exhausts the allocated time. Then, at k + 1, we select a control (in negligible computation time) from the tree that corresponds to the actual measured delay. The control is sent to the system, and depending on the delay, the system will receive the latest computed control or a previous one. In our experiment the network is simulated by artificially generating delays that are uniform random.

The computer uses an Intel Xeon E5-1620 CPU at 3.6GHz and has 16GB RAM. A C++ OMSd implementation is used. As shown in Fig. 10, the pendulum is swung up and stabilized despite the delay. A video illustrating the results can be found at http://rocon.utcluj.ro/files/ rotpend_oms.mp4.

Conclusions and future work

We have studied optimistic minimax search for adversarial switched problems, handling both the cases when the two switching signals are unconstrained, and when they must obey minimum dwell times. We have shown convergence in a well-characterized way towards the optimal (constrained) minimax value, and illustrated the algorithm numerically and in real-time control.

When the uncontrolled signal evolves along a known Markov chain, it will pay off to develop a tailored algorithm and analysis rather than conservatively assume the worst-case signal as above. Our optimistic method for stochastic Markov decision processes in [START_REF] Bus | Optimistic planning for Markov decision processes[END_REF] is suited to this problem, while the analysis will require significant changes to handle dwell time constraints.

Fig. 1 .

 1 Fig.1. Illustration of a constrained minimax sequence for d u = d w = 2. The max and min modes applied are shown by a blue continuous line and a red dashed line, respectively. Denote e.g. the max (blue) modes by 1, 2, 3 from bottom to top. At k = 1 (h = 2k = 2), the max agent has switched from mode 1 to mode 2; since its dwell time limit is 2, it must wait until at least k = 1 + 2 = 3 (equivalently, until h = 6) before it is allowed to select a new mode, different from 2. Here, it selects mode 3. In contrast, had the problem been unconstrained, the max mode could have already been changed at k = 2.

Fig. 2 Fig. 2 .

 22 Fig. 2. Example of a minimax tree developed by the algorithm from a max root. The max agent has modes 'a' and 'b', while the min agent has modes 'c' and 'd', so that Nu = Nw = 2. The dwell time limits are taken d u = d w = 2.

Fig. 3 . 1

 31 Fig. 3. Snapshot of the tree after 4 expansions. Nodes are now labeled by the interval [L, B], and dwell time labels are skipped for clarity. The thick path leads to the node that the algorithm would expand next. Algorithm 1 OMSd Input: budget n 1: initialize: T ← {z 0 }, the root 2: for iteration t = 1 to n do 3:

Fig. 4 .

 4 Fig.4. A tree with κ = 1. Rewards are shown along the transitions and inside subtrees where they remain constant. The thick path is minimax-optimal and never switches.

Fig. 6 .

 6 Fig.6. Returns in the unconstrained case. Each curve shows the evolution as n varies, for a given nw.

Fig. 7 .

 7 Fig. 7. A controlled trajectory. The modes 1, 2, or 3 chosen at each step are shown by 'x' markers.

Fig. 8 .

 8 Fig.8. Returns as the min agent dwell-time limit varies. Note that the vertical axis is kept constant in return plots to ensure they are comparable.

Fig. 9 .

 9 Fig. 9. Returns in the Nash case.

Fig. 10 .

 10 Fig. 10. Real-time trajectory of the rotational pendulum.

  2 formally states the problem, Sec. 3 gives the algorithm and Sec. 4 analyzes it. Experimental results are given in Sec. 5; Sec. 6 concludes.

2 Problem definition

2.1 Unconstrained case

Consider a switched system where a maximizer (max) agent and a minimizer (min) agent control, in turn, two different switching signals. The setting is noncooperative, i.e. the min agent acts against the max agent: while the max agent aims to maximize a cumulative reward signal, the min agent acts so as to minimize it. The max and min signals are respectively denoted u and w; there are N u and N w modes for these signals, and the sets of modes are denoted U and W .