Steady-state Based Approach to Online Non-stochastic Control

1. Problématique et Contexte

L'article s'intéresse au problème du contrôle non-stochastique en ligne (ONC). Dans ce cadre, un apprenant doit contrôler un système linéaire invariant dans le temps (LTI) face à des perturbations et des fonctions de coût convexes choisies de manière adversariale (c'est-à-dire sans connaissance a priori et potentiellement hostiles).

L'objectif est de minimiser le coût cumulé sur un horizon $T$. La performance est évaluée via le regret, qui compare le coût subi par l'algorithme en ligne à celui du meilleur contrôleur d'une classe de référence choisie a posteriori (en connaissance de cause).

Limites des approches existantes :

• La littérature classique (ex: Agarwal et al.) utilise souvent comme référence le meilleur contrôleur à rétroaction linéaire ($u_t = -Kx_t$).
• Dans une précédente étude des auteurs [13], une approche basée sur les états stationnaires atteignables par des entrées constantes a été proposée. Bien que simple et interprétable, cette classe de référence est trop restrictive : elle limite la dimension de l'espace des états à celle des entrées (problématique pour les systèmes sous-actionnés) et ignore les points d'équilibre stabilisables par des lois de commande à rétroaction.

Question centrale : Peut-on étendre cette approche par état stationnaire à une classe de référence plus riche, tout en conservant des garanties de regret sous-linéaire ?

2. Méthodologie

Les auteurs proposent un nouvel algorithme qui étend la classe de référence aux états stationnaires atteignables par des contrôleurs affines stabilisants de la forme :
$$u_t = -K x_t + v$$
où $K$ est un gain de rétroaction stabilisant et $v$ est un terme de commande constant.

A. Nouvelle Définition du Regret

Le regret est défini par rapport à la variété des états stationnaires en boucle fermée ($\mathcal{Z}$), qui est l'union de tous les états stationnaires possibles pour tous les contrôleurs affines stabilisants possibles.
$$R_{\mathcal{Z}}(T) = \sum_{t=1}^T f_t(x_t) - \min_{z \in \mathcal{Z}} \sum_{t=1}^T f_t(z)$$
Note importante : L'ensemble $\mathcal{Z}$ est non convexe (car c'est une union non dénombrable d'ensembles convexes), ce qui rend l'optimisation directe difficile.

B. L'Algorithme Proposé : BatchFTPL

Pour surmonter la non-convexité et la nécessité de changer dynamiquement de politique sans perdre la stabilité du système, les auteurs combinent deux techniques :

1. Follow-The-Perturbed-Leader (FTPL) : Une méthode d'optimisation en ligne non convexe qui ajoute du bruit (régularisation stochastique) pour explorer l'espace des solutions.
2. Stratégie de "Batching" (Regroupement par lots) :
   • L'horizon temporel est divisé en lots de taille $H$.
   • À chaque début de lot $n$, l'algorithme sélectionne un état cible $z_n \in \mathcal{Z}$ en utilisant une mise à jour FTPL approximative sur la somme des coûts du lot précédent.
   • Une fois $z_n$ choisi, l'algorithme calcule un couple $(K_n, v_n)$ tel que $z_n$ soit un point d'équilibre pour le contrôleur affine $u = -K_n x + v_n$.
   • Ce contrôleur est maintenu fixe pendant toute la durée du lot $H$.

Justification du Batching :

• Cela permet au système de se stabiliser vers l'état cible $z_n$ avant que la politique ne change, évitant ainsi les instabilités dues à des commutations trop fréquentes entre contrôleurs stables.
• Cela permet d'utiliser FTPL sur des coûts "agrégés" (par lot), réduisant la variance et la fréquence des changements de politique.

C. Hypothèses et Oracles

• L'algorithme nécessite un oracle d'optimisation approximative ($\mathcal{O}_\epsilon$) capable de trouver un minimum $\epsilon$-approché sur l'ensemble non convexe $\mathcal{Z}$.
• Les auteurs montrent qu'une solution approximative suffit pour garantir le regret.
• Une hypothèse de stabilité forte ($\gamma, \kappa$-stabilité) est utilisée pour garantir que les matrices de transition en boucle fermée décayent géométriquement.

3. Résultats Théoriques et Garanties

Le résultat principal est énoncé dans le Théorème 8 :

• Garantie de Regret : L'algorithme proposé atteint un regret espéré de l'ordre de $O(\sqrt{T})$ par rapport à la classe de référence enrichie (contrôleurs affines).
• Paramètres : Ce résultat est obtenu avec un choix approprié de la taille du lot $H$, du paramètre de régularisation $\eta$ et de la précision de l'oracle $\epsilon$.
• Stabilité : L'algorithme garantit que l'état du système reste borné, même avec des changements de politique, grâce à la taille du lot $H$ choisie spécifiquement pour assurer la décroissance géométrique de l'erreur de suivi entre les lots.

4. Résultats Expérimentaux

Les auteurs comparent leur méthode (BatchFTPL) avec l'algorithme de référence basé sur l'action de perturbation (DAC - Disturbance Action Controller) de Agarwal et al. [5].

• Configuration : Système LTI 3D avec des coûts quadratiques variables et des perturbations uniformes.
• Implémentation de l'Oracle : Pour gérer la non-convexité de $\mathcal{Z}$, ils discrétisent l'espace des gains stabilisants $K$ en un "banque" de 100 contrôleurs. Pour chaque lot, ils résolvent un problème convexe pour chaque $K$ et choisissent le meilleur.
• Performance (Coût) : BatchFTPL obtient systématiquement un coût cumulé inférieur à DAC, démontrant que la classe de référence plus riche (affine) se traduit par une meilleure performance réelle.
• Complexité Calculatoire :
  • Une seule mise à jour de BatchFTPL (appel à l'oracle) est plus coûteuse qu'une mise à jour DAC.
  • Cependant, comme l'oracle n'est appelé que tous les $H$ pas de temps, le temps d'exécution total de BatchFTPL est inférieur à celui de DAC dans leurs simulations.
  • Cela démontre que l'approche par lots peut compenser la complexité de l'optimisation non convexe par une fréquence de mise à jour réduite.

5. Contributions Clés et Signification

1. Extension de la classe de référence : Passage d'une référence basée sur des entrées constantes à une référence basée sur des contrôleurs affines stabilisants. Cela élargit considérablement l'ensemble des performances comparables et rend le benchmark plus pertinent pour les systèmes complexes.
2. Gestion de la non-convexité : Développement d'une méthode combinant FTPL et batching pour naviguer dans un espace de décision non convexe tout en maintenant la stabilité du système physique.
3. Garanties théoriques solides : Preuve que malgré la complexité accrue (non-convexité, dynamique commutée), le taux de regret optimal $O(\sqrt{T})$ est préservé.
4. Faisabilité pratique : Les simulations montrent que même avec un oracle approximatif simple (discrétisation), la méthode est compétitive en termes de performance et de temps de calcul par rapport aux méthodes de l'état de l'art.

Conclusion :
Cet article démontre que l'approche par "état stationnaire" pour le contrôle en ligne peut être généralisée au-delà des commandes constantes sans sacrifier les garanties théoriques. Bien que cela impose un coût computationnel lié à l'optimisation non convexe, la stratégie de batching permet de rendre l'approche pratique et performante, offrant une nouvelle perspective pour le contrôle robuste dans des environnements adversariaux.