Improved regret bounds in tabular RL 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 ∈ [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, √max( S, exp(ε) + 1) S A K (exp(ε) + 1)exp(ε) - 1), up to constants and a √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 Ω(HS√A Kε) and an upper bound in Õ(H² S² √ 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 √S and the previously known upper bound by a factor of H √A.