提出更高效的隐私保护强化学习算法，实现更低的累积损失。
Faster Rates for Private Adversarial Bandits
- 将非隐私算法转化为私密算法，提升隐私保护下的学习效率。
- 在ε≤1时，误差率降低至O(√KT/√ε)，优于现有方法。
- 适用于小规模动作或专家数，适合注重隐私的强化学习场景。
我们设计了用于对抗性老虎机和带专家建议老虎机的新颖差分隐私算法。对于对抗性老虎机，提出一种简单高效的非隐私算法转私密算法的方法。将其与现有非隐私算法结合后，达到上界为O(√KT/√ε)的后悔率，优于现有上界O(√KT log(KT)/ε)，对所有ε≤1均成立。特别地，当ε≤1/√T时仍能实现亚线性期望后悔率，首次建立了该问题中中心化与本地差分隐私之间的分离。对于带专家建议的老虎机，我们给出了首个差分隐私算法，其期望后悔率为O(√NT/√ε)、O(√KT log(N) log(KT)/ε)以及Õ(N^{1/6}K^{1/2}T^{2/3} log(NT)/ε^{1/3} + N^{1/2} log(NT)/ε)，其中K和N分别为动作数与专家数。这些速率使得在不同大小的K、N和ε组合下均可获得亚线性后悔率。
原文摘要 · Abstract (English)
We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conversion of any non-private bandit algorithm to a private bandit algorithm. Instantiating our conversion with existing non-private bandit algorithms gives a regret upper bound of $O\left(\frac{\sqrt{KT}}{\sqrtε}\right)$, improving upon the existing upper bound $O\left(\frac{\sqrt{KT \log(KT)}}ε\right)$ for all $ε\leq 1$. In particular, our algorithms allow for sublinear expected regret even when $ε\leq \frac{1}{\sqrt{T}}$, establishing the first known separation between central and local differential privacy for this problem. For bandits with expert advice, we give the first differentially private algorithms, with expected regret $O\left(\frac{\sqrt{NT}}{\sqrtε}\right), O\left(\frac{\sqrt{KT\log(N)}\log(KT)}ε\right)$, and $\tilde{O}\left(\frac{N^{1/6}K^{1/2}T^{2/3}\log(NT)}{ε^{1/3}} + \frac{N^{1/2}\log(NT)}ε\right)$, where $K$ and $N$ are the number of actions and experts respectively. These rates allow us to get sublinear regret for different combinations of small and large $K, N$ and $ε.$
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。