Sintesi Tecnica: Apprendimento per Rinforzo con Osservazioni Innescate dall'Azione

1. Definizione del Problema

Il documento affronta una classe specifica di Processi Decisionali Markoviani Parzialmente Osservabili (POMDP) in cui la disponibilità delle osservazioni dello stato non è esogena o fissa, ma è invece innescata dall'azione (action-triggered). Nell'RL standard, un agente osserva il nuovo stato dopo ogni azione. In molti scenari pratici (ad esempio, diagnostica clinica, trading finanziario), l'acquisizione di un'osservazione dello stato è costosa, inaffidabile o richiede un'azione specifica per essere innescata.

Gli autori formalizzano questo scenario come Processi Decisionali Markoviani con Tracciabilità Sporadica Innescata dall'Azione (ATST-MDP).

• Meccanismo: Quando un agente nello stato $s$ esegue l'azione $a$, riceve una ricompensa e l'ambiente transita verso $s'$. Fondamentalmente, $s'$ non viene sempre osservato. Con probabilità $\beta(a)$, si verifica un "evento osservativo" (un burst di dati), che rivela $s'$ e la ricompensa cumulativa dall'ultimo burst. Con probabilità $1-\beta(a)$, non viene fornito alcun feedback sullo stato.
• Sfida: L'agente deve ottimizzare simultaneamente la politica di controllo e decidere quando innescare le osservazioni (scegliendo azioni con un $\beta(a)$ più elevato) per ridurre l'incertezza, bilanciando il costo dell'acquisizione di informazioni con le prestazioni del controllo.
• Distinzione: A differenza dei POMDP standard dove le osservazioni sono rumorose ma frequenti, o dell'RL con ritardi esogeni dove il feedback è semplicemente in ritardo, gli ATST-MDP presentano ritardi endogeni, in cui le scelte dell'agente determinano direttamente la frequenza della rivelazione dello stato.

2. Metodologia

2.1 Spazio degli Stati Aumentato ed Equazioni di Bellman

Per gestire la parziale osservabilità, gli autori definiscono uno spazio degli stati aumentato $\mathcal{X} = \mathcal{S} \times \mathcal{A}^{<\infty}$. Uno stato aumentato $x = (s_1, a_1, \dots, a_n)$ consiste nell'ultimo stato osservato $s_1$ e nella sequenza di azioni intraprese da quell'osservazione.

• Sufficienza: Lo stato aumentato funge da statistica sufficiente per la storia, permettendo al problema di essere trattato come un MDP completamente osservabile su $\mathcal{X}$.
• Dinamica: La transizione su $\mathcal{X}$ è un mix: con probabilità $\beta(a)$, lo stato si resetta al nuovo stato osservato $s'$; con probabilità $1-\beta(a)$, la sequenza di azioni viene estesa ($x \leftarrow x \cdot a$).
• Equazioni di Bellman: Gli autori derivano le equazioni di ottimalità di Bellman per le funzioni di valore $V^\pi$ e $Q^\pi$ su questo spazio aumentato, provando l'esistenza di una politica aumentata ottimale $\pi^*$.

2.2 Riformulazione della Sequenza di Azioni

Riconoscendo che lo spazio degli stati aumentati si dirama all'infinito, gli autori propongono una riformulazione basata sulla struttura di rinnovo dei burst di dati. Invece di decidere azione per azione, l'agente si impegna in una sequenza di azioni $a \in \mathcal{A}^\mathbb{N}$ ad ogni burst di dati, eseguendola fino alla successiva osservazione.

• Questo trasforma il problema in un processo decisionale su $(\mathcal{S}, \mathcal{A}^\mathbb{N})$.
• La funzione di valore $K^\pi(s, a)$ rappresenta la ricompensa scontata attesa accumulata dallo stato $s$ eseguendo la sequenza $a$ fino al prossimo burst di dati, più il valore di continuazione dello stato rivelato.

2.3 Rappresentazione Lineare sotto l'Assunzione di MDP Lineare

Per rendere trattabile lo spazio infinito delle sequenze di azioni, il documento assume una struttura di MDP Lineare (Assunzione 4.1), in cui i kernel di transizione e le ricompense sono lineari rispetto a una mappa di caratteristiche $\phi(s, a)$.

• Intuizione Chiave: Sotto questa assunzione, la funzione di valore della sequenza di azioni $K^\pi$ ammette una rappresentazione lineare in una mappa di caratteristiche a dimensione finita $\psi: \mathcal{S} \times \mathcal{A}^\mathbb{N} \to \mathbb{R}^{2d}$.
• Costruzione: La mappa di caratteristiche $\psi$ è costruita utilizzando matrici di azione $M_a$ (derivate dalle dinamiche di transizione) e probabilità di osservazione $\beta_a$. Nello specifico, $\psi$ codifica l'evoluzione delle caratteristiche durante la sequenza di azioni e la probabilità che i burst di dati si verifichino in ogni passaggio.
• Risultato: $K^\pi(s, a) = \langle \psi(s, a), v^\pi_{1,2} \rangle$, dove $v^\pi_{1,2}$ è un vettore dipendente dalla politica. Ciò consente l'uso di metodi standard basati sulla regressione nonostante lo spazio delle azioni infinito.

2.4 Stima e Algoritmo di Apprendimento

Il documento propone ATST-LSVI-UCB (Least-Squares Value Iteration con Upper Confidence Bounds per l'azione innescata sporadicamente).

• Stima delle Caratteristiche: Poiché la vera mappa di caratteristiche $\psi$ è sconosciuta, l'algoritmo stima le matrici di azione $M_a$ sottostanti e le probabilità di osservazione $\beta_a$ dai dati esplorativi tramite regressione ridge e medie empiriche. I Teoremi 4.6 e la Corollario 4.9 forniscono limiti di complessità campionaria non asintotica per la costruzione di un'approssimazione $\epsilon$-ammissibile di $\psi$.
• Algoritmo: L'algoritmo opera in episodi con orizzonti geometrici. Esegue una iterazione del valore a ritroso sulla mappa di caratteristiche stimata per calcolare stime ottimistiche del valore (usando bonus UCB) ed esegue sequenze di azioni greedy.
• Ottimizzazione: Sebbene lo spazio delle azioni sia infinito, l'ottimizzazione $\max_a K(s, a)$ viene eseguita sull'immagine compatta della mappa di caratteristiche. In pratica, ciò può essere approssimato limitandosi a sequenze a profondità finita o eventualmente periodiche.

3. Contributi Chiave

1. Formalizzazione degli ATST-MDP: Un nuovo framework per l'RL in ambienti con osservazioni dello stato innescate dall'azione, colmando il divario tra gli MDP standard e i POMDP generali.
2. Fondamenti Teorici: Derivazione delle equazioni di Bellman nello spazio degli stati aumentato e prova dell'esistenza di una politica ottimale.
3. Rappresentazione Lineare: Dimostrazione che, sotto l'assunzione di MDP lineare, la funzione di valore sulle sequenze di azioni è lineare rispetto a una mappa di caratteristiche a dimensione finita, consentendo un apprendimento efficiente.
4. Algoritmo e Limiti di Regret: Proposta di un algoritmo di iterazione del valore ottimista, ATST-LSVI-UCB. Gli autori dimostrano un limite di regret di $\tilde{O}(\sqrt{d^3 K (1-\gamma)^{-3}})$ per l'apprendimento episodico, che corrisponde al tasso ottimale noto per gli MDP lineari completamente osservabili.
5. Complessità Campionaria: Stabilire i limiti di complessità campionaria per stimare la mappa di caratteristiche delle sequenze di azioni dai dati, mostrando che essa è polinomiale nella dimensione $d$ e indipendente dalla dimensione dello spazio degli stati $|\mathcal{S}|$.

4. Risultati

• Teorici: Il limite di regret corrisponde allo stato dell'arte per gli MDP lineari con piena osservabilità, nonostante la maggiore complessità della parziale osservabilità e dei ritardi innescati dall'azione. Il limite scala con la dimensione delle caratteristiche $d$, il numero di episodi $K$ e l'inverso del fattore di sconto $(1-\gamma)$.
• Empirici: Gli esperimenti su due ambienti tabulari, RiverSwim (orientato all'esplorazione) e RiverBalance (orientato alla stabilizzazione), dimostrano la validità dell'algoritmo.
  • In RiverSwim, le osservazioni sparse (basso $\beta$) hanno sorprendentemente accelerato la convergenza incoraggiando impegni open-loop più lunghi (esplorazione).
  • In RiverBalance, le osservazioni frequenti (alto $\beta$) hanno prodotto ricompense più elevate, poiché il compito richiedeva correzioni dipendenti dallo stato per mantenere la stabilità.
  • I risultati evidenziano che la frequenza ottimale di osservazione dipende dal compito.

5. Significato e Rivendicazioni

Il documento sostiene di fornire una base teorica per l'apprendimento per rinforzo in ambienti con osservazioni dello stato innescate dall'azione. La sua importanza risiede nel:

• Colmare i Divari: Affronta una classe di POMDP specifici e praticamente rilevanti (percezione attiva, sensori costosi) che i metodi generali per i POMDP faticano a gestire a causa dell'intrattabilità computazionale.
• Trattabilità: Sfruttando la struttura di rinnovo indotta dai burst di dati e l'assunzione di MDP lineare, trasforma un problema di parziale osservabilità intrattabile in un problema di regressione lineare trattabile.
• Ottimalità: Raggiunge tassi di regret comparabili alle impostazioni a piena osservabilità, suggerendo che il "costo" della tracciabilità sporadica può essere mitigato se il meccanismo di osservazione è compreso e sfruttato.
• Stima Priva di Ricompensa: La stima della mappa di caratteristiche è priva di ricompensa (reward-free), il che significa che l'apprendimento strutturale dell'ambiente (dinamiche e probabilità di osservazione) può essere scollegato dalla specifica funzione di ricompensa, permettendo un adattamento della politica flessibile.

Gli autori osservano che il lavoro futuro dovrebbe concentrarsi sulla progettazione di schemi di approssimazione efficienti per l'ottimizzazione delle sequenze di azioni infinite e sullo sviluppo di algoritmi completamente online che raffinino adattivamente le stime delle caratteristiche senza dati esplorativi pre-raccolti.