Steady-state Based Approach to Online Non-stochastic Control

1. Introducción y Planteamiento del Problema

El artículo aborda el problema del Control No Estocástico Online (ONC, por sus siglas en inglés). En este escenario, un agente (aprendiz) debe controlar un sistema lineal invariante en el tiempo (LTI) frente a una secuencia de costos convexos y perturbaciones desconocidas, seleccionadas de manera adversaria. El objetivo es minimizar el costo total acumulado a lo largo del tiempo.

El desafío principal es que el aprendiz no conoce los costos futuros ni las perturbaciones al tomar decisiones. Por lo tanto, el rendimiento se evalúa mediante el concepto de regret (arrepentimiento), que compara el costo acumulado del algoritmo online contra el de la mejor política de control dentro de una clase de referencia (benchmark) elegida a posteriori.

El problema específico:
La literatura reciente en ONC ha desarrollado algoritmos con regret sublineal comparados contra controladores de retroalimentación lineal estáticos. Sin embargo, los autores argumentan que las referencias basadas en entradas constantes (que llevan a estados estacionarios fijos) son limitantes, especialmente en sistemas subactuados o cuando se permite el uso de retroalimentación.
El objetivo de este trabajo es extender la clase de comparación a un conjunto más rico: el conjunto de estados estacionarios alcanzables bajo controladores afines estabilizantes de la forma $u_t = -Kx_t + v$, donde $K$ es una ganancia de retroalimentación que estabiliza el sistema y $v$ es un offset.

2. Metodología Propuesta

Los autores proponen un nuevo algoritmo que combina optimización no convexa online con un esquema de agrupamiento (batching) para mantener la estabilidad del sistema.

A. Definición del Nuevo Benchmark

Se define una variedad de estados estacionarios en lazo cerrado ($\mathcal{Z}$), que es la unión de todos los estados estacionarios alcanzables por cualquier controlador afín fuertemente estabilizante ($K$) y offset ($v$) dentro de un conjunto convexo de entradas.

• Desafío: A diferencia de la clase de entradas constantes (que forma un conjunto convexo), el conjunto $\mathcal{Z}$ es no convexo debido a la unión no numerable de conjuntos convexos asociados a diferentes $K$. Esto impide el uso directo de métodos de proyección estándar.

B. Algoritmo: BatchFTPL (Follow-The-Perturbed-Leader con Agrupamiento)

Para abordar la no convexidad y la necesidad de cambiar dinámicamente la política de control sin perder estabilidad, el algoritmo utiliza:

1. Optimización No Convexa (FTPL): Se basa en el marco Follow-The-Perturbed-Leader (FTPL) para optimización no convexa. En lugar de proyectar sobre un conjunto convexo, el algoritmo selecciona un estado estacionario objetivo ($z_n$) minimizando la suma de costos de un "lote" (batch) más una función de regularización aleatoria.
2. Esquema de Agrupamiento (Batching):
   • El horizonte de tiempo $T$ se divide en lotes de tamaño $H$.
   • Dentro de cada lote $n$, el controlador se mantiene fijo: $u_t = -K_n x_t + v_n$.
   • Al inicio de cada lote, se selecciona un nuevo estado objetivo $z_n \in \mathcal{Z}$ y se calculan los parámetros $(K_n, v_n)$ correspondientes.
   • Propósito del Batching: Permite que la dinámica del sistema en lazo cerrado se asiente cerca del estado estacionario objetivo antes de cambiar la política, garantizando la estabilidad global a pesar de los cambios de ganancia.

C. Oracle de Minimización Aproximada

Dado que $\mathcal{Z}$ es no convexo, encontrar el mínimo exacto es difícil. El algoritmo utiliza un Oracle de Minimización Aproximada ($\mathcal{O}_\epsilon$) que garantiza encontrar un punto con un costo dentro de $\epsilon$ del óptimo. En las simulaciones, esto se implementa discretizando el espacio de controladores estables en un banco finito y resolviendo subproblemas convexos para cada uno.

3. Contribuciones Clave

1. Extensión del Benchmark: Se amplía la clase de comparación de estados estacionarios bajo entradas constantes a estados estacionarios bajo controladores afines estabilizantes. Esto proporciona una garantía de rendimiento significativamente más fuerte, ya que la clase de referencia es mucho más rica y expresiva.
2. Algoritmo con Garantías de Estabilidad: Se propone un algoritmo que maneja la no convexidad del conjunto de referencia y la conmutación de dinámicas en lazo cerrado mediante una estrategia de agrupamiento, asegurando que el estado del sistema permanezca acotado.
3. Límites de Regret Sublineales: Se demuestra teóricamente que el algoritmo logra un regret esperado de orden $O(\sqrt{T})$ con respecto al nuevo benchmark más rico. Esto es notable porque, a pesar de la mayor complejidad del benchmark y la no convexidad, la tasa de convergencia se mantiene igual que en enfoques más simples.
4. Robustez a Perturbaciones: Aunque el análisis teórico asume inicialmente ausencia de perturbaciones para claridad, se muestra cómo extender el método al caso con perturbaciones adversarias mediante una descomposición de estados (usando un ganancia fija para la parte de perturbación).

4. Resultados y Simulaciones

Los autores realizaron experimentos numéricos comparando su método (BatchFTPL) con el algoritmo de control de acción de perturbación (DAC) de Agarwal et al. (el estado del arte anterior).

• Rendimiento: BatchFTPL consistentemente superó a DAC en términos de costo total acumulado. Esto valida que el benchmark más rico (controladores afines) se traduce en una mejora tangible en el rendimiento.
• Costo Computacional:
  • Cada llamada al oráculo de BatchFTPL es más costosa que una actualización de DAC, ya que implica resolver un problema de optimización no convexa (o una aproximación sobre un banco de controladores).
  • Sin embargo, debido a que las actualizaciones ocurren solo cada $H$ pasos (frecuencia de actualización más baja), el tiempo total de ejecución de BatchFTPL fue menor o comparable al de DAC en los experimentos realizados.
• Conclusión de las simulaciones: El enfoque propuesto es viable en la práctica y ofrece un equilibrio favorable entre rendimiento superior y costo computacional.

5. Significado e Impacto

Este trabajo es significativo porque:

• Cierre la brecha entre teoría y práctica en ONC: Muestra que es posible competir contra clases de controladores más sofisticadas (afines) sin sacrificar las garantías teóricas de regret.
• Manejo de No Convexidad: Proporciona un marco para aplicar técnicas de aprendizaje online (como FTPL) en problemas de control donde el espacio de políticas o estados objetivo es no convexo, un desafío común en sistemas reales.
• Eficiencia Operativa: Demuestra que la complejidad computacional adicional de buscar mejores políticas puede mitigarse mediante estrategias de agrupamiento, haciendo que el método competitivo en tiempo real.

En resumen, el artículo presenta un avance fundamental en el control online no estocástico, permitiendo que los sistemas aprendan a estabilizarse en los mejores estados posibles utilizando retroalimentación dinámica, con garantías matemáticas sólidas y viabilidad computacional demostrada.