Improved regret bounds in tabular RL under local differential privacy
Poster A: Monday -- 11:00 - 12:30
Hugo Richard
Keywords: Reinforcement Learning, Local differential privacy, Regret minimization
We study regret minimization for time-homogeneous
episodic tabular reinforcement learning with $S$ states and $A$ actions under
non-interactive $\epsilon$-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 $\epsilon$-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\bigg(K, \frac{ \sqrt{\max( S, \exp(\epsilon) + 1) S A K (\exp(\epsilon) +
1)}}{\exp(\epsilon) - 1}\bigg)$, 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 $\epsilon$, we show a lower bound in
$\Omega(HS\frac{\sqrt{A K}}{\epsilon})$ and an
upper bound in $\tilde{O}(H^2 S^2 \frac{\sqrt{ AK}}{\epsilon})$.
The upper bound is achieved by an algorithm based on UCBVI and a unary
encoding mechanism. For small $\epsilon$, 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}$.