Improved Regret bounds in Tabular Reinforcement Learning under Local Differential Privacy

We study regret minimization for time-homogeneous episodic tabular reinforcement learning with $S$ states and $A$ actions under non-interactive $ϵ$-local differential privacy (LDP). In each episode $k\in [K]$, the decision-maker sends a policy to a user, the user executes the policy for $H$ steps, and sends an $ϵ$-locally differentially private message back to the decision-maker. When $H=1$, the problem reduces to an LDP contextual bandit with $S$ contexts, $A$ arms and horizon $K$. We prove that the minimax regret is $\min (K,\frac{\sqrt{\max (S,\exp (ϵ)+1)SAK(\exp (ϵ)+1)}}{\exp (ϵ)-1})$, up to constants and a $\sqrt{\log (A)}$ factor. The upper bound is achieved by an adaptation of EXP3 and a unary encoding mechanism. When $H>1$, and for small $ϵ$, we show a lower bound in $\Omega (HS\frac{\sqrt{AK}}{ϵ})$ and an upper bound in $\tilde{O}(H^2{S}^2\frac{\sqrt{AK}}{ϵ})$. The upper bound is achieved by an algorithm based on UCBVI and a unary encoding mechanism. For small $ϵ$, these bounds improve the previously known lower bound by a factor $\sqrt{S}$ and the previously known upper bound by a factor of $H\sqrt{A}$.