在博弈论框架下实现隐私保护，有效控制用户信息泄露风险。
Differential Privacy in the Extensive-Form Bandit Problem
- 设计满足ε-局部差分隐私的算法，保障用户行为隐私。
- 达到约√(A ln(S)T)/ε的后悔率，性能与隐私预算相关。
- 首次研究该问题中的差分隐私，适合关注隐私安全的研究者。
我们研究扩展形式多臂赌博机问题，其中学习者（由服务器协调的用户）在每一轮中与一个盲目的对手进行扩展形式博弈，仅观察自身所处的信息集及获得的收益/损失。本文提出一种满足ε-局部差分隐私的算法，其后悔率为˜O(√(A ln(S)T)/ε)，其中A为学习者可能采取的总动作数，S为学习者可能的简化策略数，T为试验次数。每轮算法的时间复杂度，除对数因子外，等同于服务器向用户传输简化策略所需时间。局部差分隐私是差分隐私最强形式，据我们所知，这是首个研究扩展形式多臂赌博机中任何形式差分隐私的工作。
原文摘要 · Abstract (English)
We consider the extensive-form bandit problem, where on each trial the learner (a user coordinated by a server) plays an extensive-form game against an oblivious adversary, observing the information sets it finds itself in as well as the resulting payoff/loss. We give an algorithm for this problem that satisfies $ε$-local differential privacy and attains a regret of $\tilde{O}(\sqrt{A\ln(S)T}/ε)$, where $A$ is the total number of actions that the learner can possibly take, $S$ is the number of the learner's possible reduced strategies, and $T$ is the number of trials. On each trial, the time complexity of our algorithm is, up to a factor logarithmic in the maximum number of actions at an infoset, equal to the time required for the server to transmit the reduced strategy to the user. We note that local differential privacy is the strongest version of differential privacy and, to the best of our knowledge, this is the first work to study differential privacy of any form in the extensive-form bandit problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。