Limiti di regret migliorati nell’apprendimento per rinforzo tabulare con privacy differenziale locale

Abstract degli autori

Studiamo la minimizzazione del regret nell’apprendimento per rinforzo episodico tabulare omogeneo nel tempo, con $S$ stati e $A$ azioni, nel regime di privacy differenziale locale (LDP) $ε$ non interattiva. In ogni episodio $k \in [K]$, il decisore invia una policy a un utente, che la esegue per $H$ passi e rimanda al decisore un messaggio con privacy differenziale locale $ε$. Quando $H=1$, il problema si riduce a un bandit contestuale LDP con $S$ contesti, $A$ bracci e orizzonte $K$. Dimostriamo che il regret minimax è $\min\bigg(K, \frac{ \sqrt{\max( S, \exp(ε) + 1) S A K (\exp(ε) + 1)}}{\exp(ε) - 1}\bigg)$, a meno di costanti e di un fattore $\sqrt{\log(A)}$. Il limite superiore si ottiene adattando EXP3 e usando un meccanismo di codifica unaria. Quando $H > 1$ e $ε$ è piccolo, dimostriamo un limite inferiore in $Ω(HS\frac{\sqrt{A K}}ε)$ e un limite superiore in $\tilde{O}(H^2 S^2 \frac{\sqrt{ AK}}ε)$. Il limite superiore si ottiene con un algoritmo basato su UCBVI e un meccanismo di codifica unaria. Per valori piccoli di $ε$, questi limiti migliorano di un fattore $\sqrt{S}$ il limite inferiore noto in precedenza e di un fattore $H \sqrt{A}$ il limite superiore noto in precedenza.