# An optimistic planning algorithm for switched discrete-time LQR

Mathieu Granzotto, Romain Postoyan, Dragan Nesic, Jamal Daafouz, Lucian Busoniu

<figure><img src="image_1.png" /></figure>

## To cite this version:

Mathieu Granzotto, Romain Postoyan, Dragan Nesic, Jamal Daafouz, Lucian Busoniu. An optimistic planning algorithm for switched discrete-time LQR. 64th IEEE Conference on Decision and Control, Dec 2025, Rio de Janeiro, Brazil. hal-05328844

HAL Id: hal-05328844

https://hal.science/hal-05328844v1

Submitted on 23 Oct 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An optimistic planning algorithm for switched discrete-time LQR

Mathieu Granzotto, Romain Postoyan, Dragan Nešić, Jamal Daafouz and Lucian Bușoniu

**Abstract**— We introduce TROOP, a tree-based Riccati optimistic online planner, that is designed to generate near-optimal control laws for discrete-time switched linear systems with switched quadratic costs. The key challenge that we address is balancing computational resources against control performance, which is important as constructing near-optimal inputs often requires substantial amount of computations. TROOP addresses this trade-off by adopting an online best-first search strategy inspired by $A^*$, allowing for efficient estimates of the optimal value function. The control laws obtained guarantee both near-optimality and stability properties for the closed-loop system. These properties depend on the planning depth, which determines how far into the future the algorithm explores and is closely related to the amount of computations. TROOP thus strikes a balance between computational efficiency and control performance, which is illustrated by numerical simulations on an example.

## I. INTRODUCTION

Consider the problem of regulating a vehicle's speed while minimizing fuel consumption. Achieving this requires selecting the best gear (a discrete input) and throttle level (a continuous input), leading to an optimal hybrid-valued control scheme, specifically a mixed-integer problem. In view of the combinatorial nature of mixed-integer problems, it is key to balance the computational resources available against desired closed-loop system properties. Specifically, we typically want to obtain a cost close to the minimum one (near-optimality) while ensuring that the selected inputs drive the system to a desired operating region (stability). Even when the cost function is quadratic and the system dynamics are linear for each value of the discrete input, this remains computationally very challenging [1]. This latter setting describes the switched LQR problem: to determine a sequence of discrete linear modes as well as a sequence of continuous input vectors which, together, minimize switched quadratic costs along the solution of the closed-loop system. Switched problems arise in a wide range of important applications, including power systems and power electronics (like switching supplies), automotive control (like gear selection above), aircraft and air traffic control, computer disks, and network and congestion control [6]. In this work, we study the discrete-time switched LQR problem.

Work funded by the ANR under grant OLYMPIA ANR-23-CE48-0006, by the ARC under the Discovery Project DP210102600 and DP250100300, and by the CINEA under grant SeaClear2.0, No 101093822.

Mathieu Granzotto and Dragan Nešić are with the Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, VIC 3010, Australia (e-mail: {mgranzotto, dnesic} @unimelb.edu.au).

Romain Postoyan and Jamal Daafouz are with the Université de Lorraine, CNRS, CRAN, F-54000 Nancy, France (e-mails: {name.surname} @univ-lorraine.fr). J. Daafouz is also with IUF.

Lucian Bușoniu is with the Technical University of Cluj-Napoca, 400114 Cluj-Napoca, Romania (e-mail: lucian.busoniu@aut.utcluj.ro) and is a Corresponding Member of the Romanian Academy.

The switched LQR problem has received much attention, see, e.g., [11, 17, 19, 20]. The bulk of existing approaches rely on approximating the optimal value function for any state by a piecewise quadratic function, given by sets of positive semi-definite matrices [1, 2, 11, 19]. These matrices are then used to construct the discrete and continuous inputs. However, when generating tighter approximations of the optimal value function, these sets of matrices generally become exponentially large in the number of discrete modes denoted $M$ [17]. There is a need to provide algorithms for the switched LQR problem that trade control performance with computational complexity. Indeed, while several computational strategies are available, such as employing pruning strategies [11,19], exploiting a “good” initial choice of cost matrices [1], or establishing a unique periodic sequence by nesting Linear Matrix Inequalities (LMIs) [13], these approaches often fail to balance near-optimality with computational efficiency. Most relevantly, the approach of [17] characterizes a “breadth-first” exploration of all available modes of the discrete inputs, expanding all sequences of a given length. These solve a finite-horizon switched LQR problem with ever-increasing horizons (by increasing the depth of the exploration tree), thus producing ever-improving approximations of the optimal cost. Although calculated offline, this computationally intensive approach can still lead to controllers requiring complex online searches in large lists, with potentially unsatisfactory closed-loop performance, even when employing aggressive pruning strategies, see [1, Section V].

In contrast, we propose an online planning algorithm that performs a “best-first” exploration of modes, prioritizing sequences with lower costs based on the current state. We call this new (near-)optimal control algorithm TROOP (tree-based Riccati optimistic online planner). Drawing inspiration from efficient planning algorithms like $A^*$ and optimistic planning [3,9,12], the proposed approach typically eliminates many branches from exploration. That is, instead of requiring $O(M^d)$ iterations for a tree of horizon (or depth) $d$, where $M$ is the number of discrete inputs, we require $O(c^d)$ with $c \le M$, with $c$ potentially close to one in the best-case scenario. By ignoring high-cost input sequences, our method produces finite-horizon optimal control laws similar to those in [17] but with significantly reduced computational costs. This enables the efficient generation of long input sequences with desirable closed-loop properties.

Planning algorithms typically require an enumerable number of possible future states to generate the exploration tree, while the switched LQR problem involves inputs taking values in a continuous space. A key insight of the switched LQR problem is that, given any fixed and finite sequence
of discrete inputs, the optimal continuous input is given by a time-varying Ricatti equation, see, e.g., [14,15]. This removes the need to explicitly consider the continuous input or future states for planning, and instead we can concentrate on developing a tree of discrete input sequences and their associated Ricatti equations. This is in contrast to related optimistic planning algorithms [4,5], that search over continuous inputs, and [3,9,12], which explore a tree of future states, which are here unfeasible. In other words, by leveraging the switched linear structure, we significantly reduce the computational costs associated with handling continuous inputs.

A feature of TROOP is that the matrices computed are state-independent, which implies that the core and computationally intensive calculations can be saved in a cache, to be later re-used in the calculation of costs for longer sequences or other initial states. Furthermore, we allow for an initial cost function that lower bounds the optimal value function, which accelerates exploration and reduces online calculations. This is done by exploiting the structure of the switched LQR problem, providing an additional benefit of our method when compared to related optimistic planning algorithms, in particular [9].

To achieve the desired properties of TROOP, we rely on assumptions commonly used in the switched LQ literature. Specifically, we assume as in [1,11,17]–[19] that the system can be driven to the origin with bounded quadratic cost and that the stage-costs are positive definite with respect to the origin. We also impose a condition on the initial cost function which can always be enforced, made to guarantee a monotonicity property of the estimates of the optimal value function. Under these assumptions, TROOP offers tunable near-optimality and global exponential stability, both dependent on the planning horizon. Longer horizons yield tighter value function approximations and improved performance at the cost of more computations.

In sum, our approach ties together the rationales of [19] and [1], employing an online yet efficient optimistic planning algorithm based on [3,9], leveraging known bounds of the optimal value function to reduce controller complexity. Additionally, the switching sequence and feedback gain are optimized based on the current state, offering tighter near-optimality compared to offline sequence planning methods like [13]. Overall, TROOP offers a reliable framework for applications requiring both near-optimality and stability.

Due to space constraints, proofs have been omitted and are instead found in [10]

## II. PRELIMINARIES

### A. Notation

Let $\mathbb{R}$ be the set of real numbers, $\mathbb{R}_{\ge 0} := [0, \infty)$, $\mathbb{Z}_{\ge 0} := \{1, 2, \dots\}$, $\mathbb{Z}_{\ge 0} := \{0, 1, 2, \dots\}$. The notation $(x, y)$ stands for $[x^{\top}, y^{\top}]^{\top}$, where $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$ and $n, m \in \mathbb{Z}_{>0}$. We denote the Euclidean norm by $| \cdot |$. The identity map from $\mathbb{R}_{\ge 0}$ to $\mathbb{R}_{\ge 0}$ is denoted by $\mathbb{I}_{\ge 0}$, and the zero map from $\mathbb{R}_{\ge 0}$ to $\{0\} \subset \mathbb{R}$ by $\mathbf{0}$. For a (possibly infinite) sequence $\mathbf{u} = (u_0, \dots, u_{d-1})$ of $d \in \mathbb{Z}_{\ge 0} \cup \{\infty\}$ elements that take values in $\mathbb{R}^n$ with $n \in \mathbb{Z}_{>0}$, we define $\mathbf{u}_{\llap{a,b}\llap{]} := (u_a, \dots, u_b)$

with $0 \le a \le b < d$, and furthermore define $\mathbf{u}_{\llap{a,b}\llap{]} := \mathbf{u}_{\llap{0,b}\llap{]}$, $\mathbf{u}_{\llap{a,]} := \mathbf{u}_{\llap{a,d-1]\llap{]}$ and $\mathbf{u}_{\llap{d,]} := \mathbf{u}_{\llap{d,-1]\llap{]} := \emptyset$ by convention. The trace of real square matrix $A$ is denoted by $\text{tr}(A)$, while diag refers to constructing a block diagonal matrix from its arguments. The smallest and the largest eigenvalue of a real, symmetric matrix $A$ are denoted $\lambda(A)$ and $\bar{\lambda}(A)$, respectively. We write $A \succeq 0$ when real, square matrix $A$ is symmetric and positive semi-definite, and $A \succ 0$ when it is symmetric and positive definite. We write $A \succeq B$ when $A - B \succeq 0$, and $A \succ B$ when $A - B \succ 0$, for any real, symmetric matrices $A, B$. For any matrix $A \succeq 0$, $\sqrt{A}$ denotes a positive semi-definite matrix such that $\sqrt{A}^{\top} \sqrt{A} = A$. A set-valued map $F: \mathcal{X} \rightrightarrows \mathcal{Y}$ is a multivalued function that maps elements of $\mathcal{X}$ to subsets of $\mathcal{Y}$. Given a set-valued map $S: \mathbb{R}^n \rightrightarrows \mathbb{R}^m$, a selection of $S$ is a single-valued mapping $s: \text{dom} S \to \mathbb{R}^m$ such that $s(x) \in S(x)$ for any $x \in \text{dom} S$. For the sake of convenience, we write $s \in S$ to denote a selection $s$ of $S$. Function composition is denoted by $\circ$.

### B. Problem statement

Consider the system

$$x^+ = A_i x + B_i u \quad (1)$$

where $x \in \mathbb{R}^{n_x}$, $u \in \mathbb{R}^{n_u}$ and $i \in \mathbb{M} := \{1, \dots, M\}$ are the state, the continuous control input and the discrete control input, respectively, with $n_x, n_u, M \in \mathbb{Z}_{>0}$. Given $k \in \mathbb{Z}_{\ge 0}$ and a pair of sequences $\mathbf{u}_{\llap{\cdot,k}\llap{]}$, $\mathbf{i}_{\llap{\cdot,k}\llap{]}$ with elements in $\mathbb{R}^{n_u}$ and $\mathbb{M}$, respectively, we denote the solution of (1) initialized at time 0 and state $x$ by $\phi$, which thus satisfies $\phi(k, x, \mathbf{u}_{\llap{\cdot,k}\llap{]}, \mathbf{i}_{\llap{\cdot,k}\llap{]}) := A_{i_{k-1}}\phi(k-1, x, \mathbf{u}_{\llap{\cdot,k-1}\llap{]}, \mathbf{i}_{\llap{\cdot,k-1}\llap{]})+ B_{i_{k-1}}u_{k-1}$. We define the cost associated with a solution to system (1) initialized at $x$ with sequence of continuous and discrete input $\mathbf{u}$ and $\mathbf{i}$ by

$$J(x, \mathbf{u}, \mathbf{i}) := \sum_{k=0}^{\infty} \ell(\phi(k, x, \mathbf{u}_{\llap{\cdot,k}\llap{]}, \mathbf{i}_{\llap{\cdot,k}\llap{]}), u_k, i_k) \quad (2)$$

where $\ell(x, u, i) := x^{\top}Q_i x + u^{\top}R_i u$ for any $x \in \mathbb{R}^{n_x}$, $u \in \mathbb{R}^{n_u}$ and $i \in \mathbb{M}$. We assume that matrices $A_i, B_i, Q_i, R_i$ are real and of conformable dimensions, that $Q_i, R_i \succ 0$ for all $i \in \mathbb{M}$, and that system (1) is stabilizable, as formalized later in Section IV.

Given an initial state $x$, we are interested in finding sequences of continuous and discrete inputs for system (1) that minimize cost $J$. That is, ideally we wish to find for any $x \in \mathbb{R}^{n_x}$ an optimal policy, i.e., the optimal sequences of continuous and discrete inputs giving the optimal value function

$$V^*(x) := \min_{\mathbf{u},i} J(x, \mathbf{u}, i), \quad (3)$$

assuming it exists. The optimal policy can be constructed from an optimal feedback law $h^*$, which is a function obtained from the set-valued map $H^*: \mathbb{R}^{n_x} \rightrightarrows \mathbb{R}^{n_u} \times \mathbb{M}$, where

$$H^*: x \mapsto \underset{(u,i)}{\operatorname{argmin}} \{\ell(x, u, i) + V^*(A_i x + B_i u)\}, \quad (4)$$

by making a single choice for the continuous and discrete input for each possible state, i.e., $h^* \in H^*$.

Solving (3)-(4) is known to be challenging in general, with
[17] suggesting that it may be NP-hard due to the combinatorial growth of possible switching sequences. While an exact formulation of the optimal value function remains an open problem, it is known that this function can be approximated arbitrarily closely by using a finite but exponentially growing set of quadratic functions [17,19].

To overcome the computational complexity of solving (3) exactly, we propose a near-optimal point-wise algorithm for the switched LQR problem. By focusing on obtaining accurate estimates of the value function at a given initial state, rather than attempting to solve it across the entire state space, we significantly reduce the computational burden. In this way, we can close the loop of system (1) with our algorithm, generating inputs that provide desirable guarantees of near-optimality and exponential stability for the controlled system. This new algorithm, called TROOP, is inspired by optimistic planning algorithms in [3,9,12]. We provide explicit relationships between the stability of the system controlled by TROOP, its near-optimality guarantees, and a tuning parameter related to the maximum amount of computations in a sense given later, under given assumptions.

The algorithm is presented in the next section after some preliminaries.

### III. TROOP

The algorithm we present approximates $V^*(x)$ in (3) at any given $x \in \mathbb{R}^{n_x}$ by solving finite-horizon optimal control problems with a sufficiently large horizon, with or without a terminal cost. As we will see in the sequel, the finite-horizon optimal value function is calculated exploiting time-varying Riccati equations given sequences of discrete inputs, without the need to calculate the continuous input. This allows for the application of optimistic planning methods [3,9,12], which explore countable and finite combination of discrete inputs in an efficient manner.

#### A. Finite-horizon optimal control

Given $x \in \mathbb{R}^{n_x}$ and a finite horizon $d$, consider the $d$-horizon cost $J_d$, defined as

$$ J_d(x, \mathbf{u}, \mathbf{i}) := \sum_{k=0}^{d-1} \ell(\phi(k, x, \mathbf{u}_{[\cdot, k]}], \mathbf{i}_{[\cdot, k]}], u_k, i_k) + J_0(\phi(d, x, \mathbf{u}, \mathbf{i})), \quad (5) $$

with $J_0(x) := x^\top \underline{P} x$ for some designed $\underline{P} \succeq 0$ of conformable dimensions. We also introduce the optimal value function for cost (5) for a given fixed sequence of discrete inputs $\mathbf{i}$ of length $d \in \mathbb{Z}_{\ge 0}$ and a given $x \in \mathbb{R}^{n_x}$, that is

$$ V_d^\circ(x, \mathbf{i}) := \min_{\mathbf{u}} J_d(x, \mathbf{u}, \mathbf{i}). \quad (6) $$

The minimization in (6) is intentionally performed only over the sequence of continuous inputs in $J_d(x, \cdot, \mathbf{i})$, while the sequence of discrete inputs $\mathbf{i}$ remains fixed. This formulation leads to a finite-horizon time-varying LQR problem for which the optimal cost optimal value function satisfies, for any $x \in \mathbb{R}^{n_x}$ and $\mathbf{i}$ of length $d \in \mathbb{Z}_{\ge 0}$,

$$ V_d^\circ(x, \mathbf{i}) = \min_{\mathbf{u}} \{\ell(x, u, i_0) + V_{d-1}^\circ(A_{i_0}x + B_{i_0}u, \mathbf{i}_{[1, \cdot]})\}, \quad (7) $$

the Riccati operator associated with mode $i \in \mathbb{M}$ as $R_i : \mathbb{R}^{n_x \times n_x} \rightarrow \mathbb{R}^{n_x \times n_x}$, which is given by

$R_i(P) := Q_i + A_i^\top P A_i - A_i^\top P B_i (R_i + B_i^\top P B_i)^{-1} B_i^\top P A_i$ (8) for any $P \in \mathbb{R}^{n_x \times n_x}$. Note that $R_i(P) \succ 0$ whenever $P \succeq 0$ as $Q_i, R_i \succ 0$ for all $i \in \mathbb{M}$ by a Schur complement test. The next proposition shows that $V_d^\circ$ in (6) can be reduced to a quadratic form involving (8).

**Proposition 1:** Given $d \in \mathbb{Z}_{\ge 0}$, for any $d$-length sequence of discrete inputs $\mathbf{i}$, $V_d^\circ(x, \mathbf{i}) = x^\top P_i x$ for any $x \in \mathbb{R}^{n_x}$ where $P_i \succ 0$ is defined as

$$ P_i := R_{i_0} \circ R_{i_1} \circ \dots \circ R_{i_{d-1}}(\underline{P}). \quad (9) $$

Moreover,

$$ V_d^\circ(x, \mathbf{i}) = \ell(x, -K_i x, i_0) + V_{d-1}^\circ((A_{i_0} - B_{i_0} K_i)x, \mathbf{i}_{[1, \cdot]}) \quad (10) $$

$$ \text{with } K_i := (R_{i_0} + B_{i_0}^\top P_i \mathbf{1}_{[1, \cdot]}) B_{i_0})^{-1} B_{i_0}^\top P_i \mathbf{1}_{[1, \cdot]} A_{i_0}. \quad \square $$

Proposition 1 shows that $V_d^\circ$ is given by a quadratic form and that the first element of the optimal $d$-long sequence of continuous inputs is $-K_i x$. In this way, we are able to construct matrices $P_i \succ 0$ and sequences $\mathbf{u}$ such that $V_d^\circ(x, \mathbf{i}) = x^\top P_i x = J(x, \mathbf{u}, \mathbf{i})$ given discrete sequences $\mathbf{i}$ in a simple and straightforward manner in (9) and (10) in terms of (8).

So far in this section, the sequence of discrete inputs $\mathbf{i}$ is fixed, we now relax this requirement and analyze $V_d^\circ(x, \cdot)$ for any $x \in \mathbb{R}^{n_x}$.

#### B. Finite-horizon value functions

TROOP aims to produce a monotonically increasing sequence of estimates of the value function that converge to the optimal value function $V^*$ in (3) from below. For this purpose, we make the next assumption on matrix $\underline{P}$, i.e., on the terminal cost in (5).

**Condition 1 (C1):** Matrix $\underline{P} \succeq 0$ is such that, for any $i \in \mathbb{M}$,

$$ \left[ \begin{array}{cc} A_i^\top P A_i - \underline{P} + Q_i & A_i^\top P B_i \\ B_i^\top P A_i & R_i + B_i^\top P B_i \end{array} \right] \succeq 0. \quad (11) $$

C1 is made without loss of generality as matrix $\underline{P}$ is a design parameter which we are free to choose, and there always exists some matrix $\underline{P} \succeq 0$ verifying (11). Indeed, it suffices to take $\underline{P} = 0$ as $Q_i, R_i \succ 0$ for all $i \in \mathbb{M}$. Other candidates for $\underline{P}$ can be calculated by solving the LMI in (11). Interestingly, when $M = 1$, maximizing tr($\underline{P}$) under (11) leads to the optimal value function for the infinite-horizon standard (non-switched) LQR problem whenever $(A_1, B_1)$ stabilizable and $(A_1, Q_1)$ detectable [16].

C1 in conjunction to Proposition 1 leads to the next two statements.

**Proposition 2:** Let $d \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$, for any discrete inputs sequence $\mathbf{i}$ of length $d$ and any $i \in \mathbb{M}$,

$$ V_d^\circ(x, \mathbf{i}) \le V_{d+1}^\circ(x, \mathbf{i} \oplus i) \quad (12) $$

$$ \text{where } (\mathbf{i} \oplus i)_{[\cdot, d-1]} := \mathbf{i} \text{ and } (\mathbf{i} \oplus i)_{[d, d]} := \mathbf{i}. \quad \square $$

Proposition 2 shows that cost $V_d^\circ$ may only increase in $d$. As extending a sequence of discrete inputs, i.e., increasing the horizon in (5), results in a higher or equal cost, we can thus discard sequences with high cost and focus on the more promising ones. This fact will be used in the proposed algorithm as, when comparing sequences of different lengths
and costs, the sequence with a smaller associated cost $V^\circ$ is preferable to be extended as the larger ones are guaranteed to always produce larger costs as measured by $V^\circ$ by Proposition 2.

The proposed algorithm also relies on the next property of finite-horizon costs (5).

**Proposition 3:** For any $d \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$, there exists a $d$-length sequence $i^{d,*}$ such that, for any $\bar{d}$-length sequence $i$ with $\bar{d} \ge d$,

$$V_d^*(x) := V_d^\circ(x, i^{d,*}) \le V_{\bar{d}}^\circ(x, i). \quad (13)$$

In addition,

$$V_d^*(x) \le J(x, u, i) \quad (14)$$

for any infinite-length sequence of continuous and discrete inputs $u, i$ such that $\lim_{k \to \infty} \phi(k, x, u, i) = 0$. □

Proposition 3 establishes the existence of an optimal sequence of discrete inputs for cost (5) corresponding to the optimal value function $V_d^*(x)$, which is non-decreasing in $d$ by Proposition 2. Moreover, $V_d^*$ lower-bounds the incurred cost of any stabilizing sequence of inputs. Hence, $V_d^*$ also lower bounds the optimal value function for the original infinite-horizon cost (3), provided it exists and solutions to system (1) in closed-loop with $H^*$ are stabilizing, which will be established later.

We are ready to describe how a planning approach can efficiently calculate discrete inputs $i^{d,*}$ and cost $V_d^*(x)$ given $x \in \mathbb{R}^{n_x}$.

### C. The TROOP algorithm

For any given state $x \in \mathbb{R}^{n_x}$ and horizon $d \in \mathbb{Z}_{\ge 0}$, TROOP explores trees by prioritizing branches that are most promising based on current cost estimates. In an optimistic sense, the “best” candidate for the infinite-horizon optimal cost is the sequence with the smallest evaluated cost (5). By exploring the most promising sequences, TROOP reduces the computational complexity of solving the switched LQR problem while maintaining stability and performance guarantees. Specifically, the algorithm avoids exploring all branches that incur costs larger than $V_d^*(x)$.

The method is given in Algorithm 1. At each step, TROOP selects for exploration the sequence of discrete inputs that has the lowest cost calculated so far. This sequence is extended by adding new discrete inputs, and their cost are evaluated in terms of positive semi-definite matrices that solve (6). The process continues until horizon $d$ is reached.

The notation of Algorithm 1 is as follows. We denote by $\mathcal{T}$ the exploration tree from initial state $x \in \mathbb{R}^{n_x}$, constructed from discrete input sequences $i$ of length $d$, with respective cost $V_d^\circ(x, i)$. A node $N$ payload (or data) is a triplet in $\mathbb{M}^d \times \mathbb{R}^{n_x \times n_x} \times \mathbb{R}_{\ge 0}$ for some $d \in \mathbb{Z}_{\ge 0}$. These are, respectively: the label of the node which is given by the discrete input sequence, denoted by $i(N)$; the quadratic matrix that generates cost $V_d^\circ(\cdot, i(N))$, denoted by $P(N)$; and the point-wise cost $V_d^\circ(x, i(N))$, denoted by $J(N)$. A leaf is a node of $\mathcal{T}$ with no children, and the set of all leaves of $\mathcal{T}$ is denoted $L(\mathcal{T})$. At iteration $j \in \mathbb{Z}_{\ge 0}$, a leaf $L_j \in L(\mathcal{T})$ is fully expanded by extending the sequence of discrete inputs of $L_j$, denoted by $i(L_j)$. That is, for every $i \in \mathbb{M}$, we add a child to $L_j$ labeled by $s^i := \{i(L_j), i\}$,

### Algorithm 1 TROOP

**Input:** State $x$, horizon $d$.

**Output:** Sequence $i^{d,*}(x)$, cost $V_d^*(x)$, budget $\mathcal{B}$.

1: Initialization:

$$j \leftarrow 0, S \leftarrow \emptyset \\ \mathcal{T} \leftarrow \{\emptyset, \underline{P}, x^\top \underline{P} x\}$$

▷ sequence and data

2: repeat

$$j \leftarrow j + 1$$

▷ tree exploration

3: Find a leaf $L$ that minimize $J(L) = x^\top P_i(L)x$

$$L_j \in \underset{L \in \mathcal{T}}{\operatorname{argmin}} J(L) \quad (\text{OP.1})$$

$$\mathcal{T} \leftarrow \mathcal{T} \setminus L_j$$

4: Add the children of $L_j$ to $\mathcal{T}$

For all $i \in \mathbb{M}$ and $s^i := \{i(L_j), i\}$,

$$P_{s^i} := \mathcal{R}_{s_0^i} (P_{s^i_{[1:\cdot]}}) \quad (\text{OP.2})$$

$$\mathcal{T} \leftarrow \mathcal{T} \cup \{s^i, P_{s^i}, x^\top P_{s^i} x\}$$

$$5: \text{ until length}(i(L_j)) = d$$

▷ stopping criterion

$$6: S \leftarrow L_j, \text{ return } i(S), J(S), \mathcal{B} \leftarrow j.$$

which are new leaves of $\mathcal{T}$; such leaves have an associated cost matrix given by $P_{s^i}$ given by (8)-(9) and point-wise cost given by $x^\top P_{s^i} x$; after this, $L_j$ is no longer a leaf, but becomes an inner node. The algorithm repeats this process until it finds a leaf $S$ with a sequence of length $d$, and the computational resources utilized for exploring the tree are denoted as a budget $\mathcal{B} \in \mathbb{Z}_{\ge 0}$, which corresponds to $\mathcal{B}$ leaf expansions. Leaf $S$ verifies $i^{*,d} = i(S)$ and $V_d^*(x) = J(S)$, as seen in the next proposition.

**Proposition 4:** For every $d \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$, Algorithm 1 terminates with finite budget $\mathcal{B} \le \mathcal{B}^* := \frac{M^{d+1}-1}{M-1}+1$. Moreover, $i^{d,*}(x) = i(S)$ and $V_d^*(x) = J(S)$ hold. □

Proposition 4 implies that TROOP solves the optimal finite-horizon problem (13), and terminates within at most $\mathcal{B}^*$ iterations. Note that $\mathcal{B}^*$ is a very conservative estimate based on the worst case exploration, in which case TROOP behaves as a brute-force algorithm. In practice, TROOP typically requires much fewer iterations by only exploring a few branches, see Section V for examples.

In the remainder of the paper, we relate the finite-horizon optimal control problem solved by TROOP to the original infinite-horizon optimal control problem solved by Section II, in a way that allows us to determine a suitable $d$ with explicit near-optimality and stability guarantees. The corresponding analysis is inspired by [7,9] and extends to the case of a non-zero terminal cost.

## IV. GUARANTEES

In the previous section, we established that TROOP solves the optimal finite-horizon problem for cost (5). We now establish TROOP as a tool to approximate $V^*$. In addition to the requirement on $P$ in C1, we require for this purpose some extra but mild assumptions.

### A. Stabilizability assumption

The next assumption may be verified by constructing inputs that drive the system to the origin sufficiently fast and with quadratic upper-bound on the incurred cost.
**Standing Assumption 1 (SA1):** There exist a real matrix $\bar{P} > 0$ and some sequence of inputs $\mathbf{u}(x)$ and $\mathbf{i}(x)$ such that $V^*(x) = J(x, \mathbf{u}(x), \mathbf{i}(x)) \le x^\top \bar{P} x$ for any $x \in \mathbb{R}^{n_x}$. $\square$

Given the existence of $V^*$, a sufficient condition for the upper-bound is $(A_i, B_i)$ stabilizable for at least one $i \in \mathbb{M}$. In this case, a suitable $\bar{P}$ is obtained by solving $A_{\text{cl}}^{\top} \bar{P} A_{\text{cl}} - \bar{P} = -Q_i - (K^0)^{\top} R_i K^0$ with $A_{\text{cl}} := (A_i - B_i K^0)$ for $K^0 \in \mathbb{R}^{n_u \times n_x}$ such that $A_i - B_i K^0$ is Schur.

SA1 implies the next property on the optimal value function and optimal inputs. The proof is omitted as it is a direct application of Propositions 3 and 4.

**Lemma 1:** For any $x \in \mathbb{R}^{n_x}$,

$$V_d^*(x) \le V^*(x) \le x^\top \bar{P} x. \quad (15)$$

Moreover, $\lim_{k \to \infty} \phi(k, x, \mathbf{u}^*(x), \mathbf{i}^*(x)) = 0$ for sequences $\mathbf{u}^*(x)$ and $\mathbf{i}^*(x)$ such that $V^*(x) = J(x, \mathbf{u}^*(x), \mathbf{i}^*(x))$. $\square$

Lemma 1 ensures that $V_d^*$ calculated by Algorithm 1 lower bounds the optimal value function $V^*$, and moreover that solutions to (1) in closed-loop with optimal inputs converge to the origin.

We now define key constants that characterize the stability and near-optimality properties provided by TROOP.

## B. Key constants

In the remainder of this section, we unravel the relationship of both the horizon $d$ and the initial cost function $\underline{P}$ to the stabilizing and the induced near-optimality properties of TROOP. Specifically, we show that large horizons lead to exponential convergence to the origin of any solution to the corresponding closed-loop system, as well as tighter near-optimality bounds. Moreover, the required horizon decreases when the initial value functions are closer to the optimal value.

To make explicit the above relationship, we introduce $\alpha \in (0, 1)$ and $\alpha_0 > 0$ sufficiently small verifying, for all $i \in \mathbb{M}$,

$$\alpha \bar{P} \preceq Q_i \qquad \alpha_0 (\bar{P} - \underline{P}) \preceq Q_i. \quad (16)$$

As $\bar{P}, Q_i > 0$ and $\underline{P} \succeq 0$ are known matrices, the only unknowns in (16) are the scalars $\alpha$ and $\alpha_0$. Such inequalities are always feasible, since the choice $\alpha = \alpha_0 = \min_i \lambda(Q_i) / \bar{\lambda}(\bar{P})$ satisfies (16). This choice provides a simple, explicit, and conservative lower bound, while the maximum feasible values of $\alpha$ and $\alpha_0$ can be efficiently computed using LMI solvers. It is important to note that $\alpha$ is related to the guaranteed decay rate<fnref n="1" /> to the origin of solutions to system (1) in closed-loop with $H^*$ in (4), while $\alpha_0$ is related to the initial near-optimality gap, as $V_0^*(x) = x^\top \underline{P} x \le V^*(x) \le x^\top \bar{P} x$ under SA1. That is, larger $\alpha$ is related to faster exponential decay, while larger $\alpha_0$ is related to smaller initial near-optimality gap. Together, they dictate how large $d$ must be in order to provide stability and near-optimality properties for TROOP, as we establish next.

## C. Stability guarantees

We consider system (1) in closed-loop with Algorithm 1 with a given horizon $d \in \mathbb{Z}_{\ge 0}$ for all $x \in \mathbb{R}^{n_x}$, that is,

$$x^+ \in \{A_i x + B_i u \mid (u, i) \in H_d^*(x)\} := F_d(x) \quad (17)$$

for all $x \in \mathbb{R}^{n_x}$ where $H_d^*(x) := \{(u, i) \in \mathbb{R}^{n_u} \times \mathbb{M} \mid V_d^*(x) = \ell(x, u, i) + V_{d-1}^*(A_i x + B_i u)\}$. Note that $(-K_i^*(x), \mathbf{i}_0(S)) \in H_d^*(x)$ with $\mathbf{i}_0(S)$ generated by Algorithm 1 and $K_i^*(S)$ defined in Proposition 1. The notation $\phi_d^*$ stands for solutions to (17), i.e., $\phi_d^*$ verify $\phi_d^*(k+1, x) \in F_d(\phi_d^*(k, x))$ and $\phi_d^*(0, x) = x$ for any $x \in \mathbb{R}^{n_x}$ and $k \in \mathbb{Z}_{\ge 0}$.

We establish global exponential stability for system (17) provided $d$ is sufficiently large to guarantee exponential decrease.

**Theorem 1:** Let $d > \max\{1, \frac{\log \alpha_0 \alpha}{\log 1 - \alpha} + 1\}$ with $\alpha$ and $\alpha_0$ verifying (16). Then, for any $x \in \mathbb{R}^{n_x}$,

$$|\phi_d^*(k, x)| \le \beta \lambda_d^k |x| \quad (18)$$

$$\text{with } \lambda_d := 1 - \alpha + \frac{(1-\alpha)^{d-1}}{\alpha_0} \in (0, 1) \text{ and } \beta := \frac{\bar{\lambda}(\bar{P})}{\min_i \lambda(Q_i)}. \quad \square$$

Theorem 1 shows that global uniform exponential stability of the origin is achieved provided that the horizon $d$ is sufficiently large. Moreover, the decay rate $\lambda_d$ decreases up to $1 - \alpha$ as $d \to \infty$. This theorem thus provides a guaranteed upper-bound on the exponential decay rate of solutions to system (17), which can be made as close as desired to the nominal guaranteed decay rate $1 - \alpha$, at the cost of more computations. The required number of computations not only depends on the decay rate estimate $1 - \alpha$, but also on the initial mismatch between the optimal value function and cost $V_0^*$, captured by $\bar{P} - \underline{P}$. Indeed, as $\bar{P}, \underline{P} \to V^*$, $\alpha_0 \to \infty$. This implies that good initial bounds on $V^*$ reduce the required number of iterations for stability, as desired.

We now provide near-optimal guarantees for the obtained cost $V_d^*$ and for system (17).

## D. Near-optimality guarantees

The next result upper-bounds the gap between the optimal cost and the cost computed by TROOP, and such upper-bound is shown to decrease exponentially fast as we increase the horizon $d$. Thus, increasing $d$ leads to increasingly accurate approximations of the optimal value function.

**Theorem 2:** For any $d > 1$ and $x \in \mathbb{R}^{n_x}$,

$$V^*(x) - V_d^*(x) \le 1/\alpha_0 (1-\alpha)^{d-1} x^\top \bar{P} x \quad (19)$$

$$\text{holds with } \alpha \in (0, 1) \text{ and } \alpha_0 \text{ as in (16)}. \quad \square$$

In Theorem 2, we see that the cost computed by Algorithm 1 approaches $V^*$ as close as desired, provided we take $d$ sufficiently large. Moreover and similarly to Theorem 1, the near-optimality bound is small when the initial “uncertainty” captured by $\alpha_0$ also is. Indeed, when $\alpha_0 \to \infty$, the error bound in (19) goes to zero.

Theorem 2 allows for the next relative near-optimality property, and follows for the same reasons as Theorem 2, hence the proof is omitted.

**Proposition 5:** For any $d > 1$ and $x \in \mathbb{R}^{n_x} \setminus \{0\}$,

$$\frac{V^*(x) - V_d^*(x)}{V^*(x)} \le 1/\alpha_0 (1-\alpha)^{d-1} \quad (20)$$

$$\text{holds with } \alpha \in (0, 1) \text{ and } \alpha_0 \text{ as in (16)}. \quad \square$$

The above results demonstrate that TROOP produces inputs with stability and near-optimality properties, provided that the horizon is large enough for the chosen terminal cost. We illustrate the computational aspects of Algorithm 1 in an example in the next section.

<footnote n="1">¹This will become clear later, see (18) with $d = \infty$.</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 1: Respectively, Budgets and the Value function for $d=19$ and $x \in \{(\cos(\theta), \sin(\theta)), \theta \in (0, \pi)\}$, where colors blue and green indicates $i_d^* = 1$ and 2, respectively. $V^*(x)$ is guaranteed to be inside the blue and green patches.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2: The brute-force tree for $d = 5$. For $x = (-1, 0)$, TROOP explores the tree $\mathcal{T}$ in blue and selects leaf $\star$ whose sequence is in magenta.</figcaption></figure>

## V. EXAMPLE

We consider the example in [19] with $n_x = 2, n_u = 1$ and $M = 2$, whose data is given in Table I. We take $Q_1 = Q_2 = \mathbb{I}_2$ and $R_1 = R_2 = 1$. Since $(A_1, B_1)$ is controllable, $SA1$ holds and we construct $\bar{P}$ by solving the LQR problem associated with mode $i = 1$. Thus, we estimate $\alpha \approx 0.14$. All that remains is to find $\underline{P}$ that verifies C1, which we do so by maximizing $\mathrm{tr}(\underline{P})$ subject to (11) via an LMI. We find that $\alpha_0 \approx 0.53$ by solving the LMI corresponding to (16). Hence, we must employ $d > 18$ to invoke Theorem 1 stability guarantees, for which a brute-force approach requires at least $2^{20} - 1 \approx 10^6$ iterations.

We apply TROOP to the example with $d = 19$. The associated budgets are shown in Figure 1a, and we see $B_{\text{mean}} \approx 22$ and $B_{\text{max}} = 26$. It appears that the horizon scales almost linearly with the number of iterations in this example. This attests the massive reduction in computations to reach high-depth sequences, as a breadth-first approach would require $10^6$ iterations to reach a similar horizon. We plot in Figure 1b the initial lower and upper bounds of $V^*$ given by $\underline{P}$ and $\bar{P}$, as well as the theoretical guaranteed bounds for $V^*$ given the calculated $V_d^*$ with $d = 19$ by Theorem 2. Interestingly, TROOP actually finds the optimal value function up to machine precision for all points in this example for horizon $d \le 15$. Indeed, for some $d(x) \le 15$ we numerically obtain $(V_{d(x)}^* - V_{d(x)-1}^*)(x) \approx -10^{-15}$, hence $V_{d(x)}^*(x) < V_{d(x)-1}^*(x)$, which is not possible in view of Proposition 3. This indicates that the lower bound on $d$ incurs significant conservatism. We will investigate such conservatism in future work by employing a fine-tuned stopping criterion similar to [8].

## VI. CONCLUSION

By balancing computational efficiency with near-optimal performance and stability, TROOP demonstrates potential for application in fields such as robotics, automotive systems, and aerospace, where both stability and near-optimality are essential. A key advantage of TROOP over ad hoc methods is its ability to compute the value function with known

$$A_1 := \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix} \quad A_2 := \begin{bmatrix} 2 \\ 0 \end{bmatrix} \quad \bar{P} := \begin{bmatrix} 6.91 & 1.32 \\ 1.32 & 1.92 \end{bmatrix}$$

$$B_1 := \begin{bmatrix} 1 \\ 1 \end{bmatrix} \quad B_2 := \begin{bmatrix} 1 \\ 2 \end{bmatrix} \quad \underline{P} := \begin{bmatrix} 5.05 & 1.40 \\ 1.40 & 1.5 \end{bmatrix}$$

<caption>TABLE I Example Data</caption>

bounds, ensuring near-optimality and providing a point of reference for evaluating heuristic methods lacking formal performance guarantees.

In future work, we plan to reduce the conservatism in horizon $d$ for stability purposes by designing a suitable stopping criterion, as well as to relax the condition that $Q_i > 0$ for any $i \in \mathbb{M}$ and replacing it with a detectability condition.

## REFERENCES

[1] D. Antunes and W. P. M. H. Heemels, “Linear quadratic regulation of switched systems using informed policies,” *IEEE Trans. Autom. Control*, vol. 62, no. 6, pp. 2675–2688, 2017.

[2] R. Beumer, M. Van De Molengraft, and D. Antunes, “Complexity-bounded relaxed dynamic programming,” in *62nd IEEE Conf. Decis. Control.*, Singapore, Singapore, Dec. 2023, pp. 4279–4284.

[3] L. Bušoniu and R. Munos, “Optimistic planning for Markov decision processes,” in *Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics*, vol. 22. La Palma, Canary Islands: PMLR, 21–23 Apr 2012, pp. 182–189.

[4] L. Bušoniu, E. Páll, and R. Munos, “Continuous-action planning for discounted infinite-horizon nonlinear optimal control with Lipschitz values,” *Automatica*, vol. 92, pp. 100–108, Jun. 2018.

[5] L. Bušoniu, A. Daniels, R. Munos, and R. Babuska, “Optimistic planning for continuous-action deterministic systems,” in *IEEE Symp. on ADPRL*, Singapore, Singapore, Apr. 2013, pp. 69–76.

[6] S. S. Ge and Z. Sun, *Switched Linear Systems: Control and Design*, ser. Communications and Control Engineering. London: Springer, 2005.

[7] M. Granzotto, R. Postoyan, L. Bušoniu, D. Nešić, and J. Daafouz, “Finite-horizon discounted optimal control: stability and performance,” *IEEE Trans. Autom. Control*, vol. 66, no. 2, pp. 550–565, 2021.

[8] ——, “When to stop value iteration: Stability and near-optimality versus computation,” in *Proceedings of the 3rd Conference on Learning for Dynamics and Control*. PMLR, May 2021, pp. 412–424.

[9] ——, “Stable near-optimal control of nonlinear switched discrete-time systems: An optimistic planning-based approach,” *IEEE Trans. Autom. Control*, vol. 67, no. 5, pp. 2298–2313, 2022.

[10] M. Granzotto, R. Postoyan, D. Nešić, J. Daafouz, and L. Bušoniu, “An optimistic planning algorithm for switched discrete-time LQR,” https://arxiv.org/abs/2508.19054, 2025.

[11] T. Hou, Y. Li, and Z. Lin, “An improved method for approximating the infinite-horizon value function of the discrete-time switched lqr problem,” *IFAC-PapersOnLine*, vol. 56, no. 2, pp. 4138–4143, 2023.

[12] J.-F. Hren and R. Munos, “Optimistic planning of deterministic systems,” in *Recent Advances in Reinforcement Learning*. Springer, 2008, pp. 151–164.

[13] J.-W. Lee, “Infinite-horizon joint LQG synthesis of switching and feedback in discrete time,” *IEEE Trans. Autom. Control*, vol. 54, no. 8, pp. 1945–1951, Aug. 2009.

[14] B. Lincoln and B. Bernhardsson, “Efficient pruning of search trees in LQR control of switched linear systems,” in *39th IEEE Conf. Decis. and Control*, vol. 2, Sydney, Australia, 2000, pp. 1828–1833.

[15] ——, “LQR optimization of linear system switching,” *IEEE Trans. Autom. Control*, vol. 47, no. 10, pp. 1701–1705, 2002.

[16] L. Vandenberghe and V. Balakrishnan, “Semidefinite programming duality and linear system theory: Connections and implications for computation,” in *38th IEEE Conf. Decis. and Control*, vol. 1, Phoenix, United States, 1999, pp. 989–994 vol.1.

[17] W. Zhang, J. Hu, and A. Abate, “On the value functions of the discrete-time switched LQR problem,” *IEEE Trans. Autom. Control*, vol. 54, no. 11, pp. 2669–2674, 2009.

[18] ——, “A study of the discrete-time switched LQR problem,” *Purdue e-Pubs*, 2009.

[19] ——, “Infinite-horizon switched LQR problems in discrete time: A suboptimal algorithm with performance analysis,” *IEEE Trans. Autom. Control*, vol. 57, no. 7, pp. 1815–1821, 2012.

[20] J. Zhao, M. Gan, and G. Chen, “Optimal control of discrete-time switched linear systems,” *J. Frank. Inst.*, vol. 357, no. 9, pp. 5340–5358, 2020.