arXiv:2403.00036

Influencing Bandits: Arm Selection for Preference Shaping

Viraj Nadkarni, D. Manjunath, Sharayu Moharir

제출 2024-02-29

원문 초록

We consider a non stationary multi-armed bandit in which the population preferences are positively and negatively reinforced by the observed rewards. The objective of the algorithm is to shape the population preferences to maximize the fraction of the population favouring a predetermined arm. For the case of binary opinions, two types of opinion dynamics are considered -- decreasing elasticity (modeled as a Polya urn with increasing number of balls) and constant elasticity (using the voter model). For the first case, we describe an Explore-then-commit policy and a Thompson sampling policy and analyse the regret for each of these policies. We then show that these algorithms and their analyses carry over to the constant elasticity case. We also describe a Thompson sampling based algorithm for the case when more than two types of opinions are present. Finally, we discuss the case where presence of multiple recommendation systems gives rise to a trade-off between their popularity and opinion shaping objectives.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2606.21757v1cs.LG공통 태그 Recommendation Systems, Thompson Sampling

AdaPrivate-TS: Private Thompson Sampling for Contextual Bandits with Privacy Amplification

우리는 Thompson Sampling과 배치 zCDP 합성을 결합한 차등 프라이버시(differentially private) 문맥적 밴딧 알고리즘인 AdaPrivate-TS를 제안한다. 핵심 통찰은 차등 프라이버시 노이즈가 사후 공분산을 구조적인 방식으로 팽창시킨다는 점이다. 즉, $b$에 가우시안 노이즈 $N(0,σ^2 I)$를 추가하면 샘플링 공분산이 $v^2 A^{-1} + σ^2 A^{-2}$가 되며, Thompson Sampling은 이를 순수한 손상이 아닌 불확실성 증가로 해석한다. 확률적 문맥 하에서의 이벤트 수준 프라이버시(개별 상호작용 보호)의 경우, 병렬 합성이 배치 전반에 걸쳐 노이즈를 분산시키기 때문에 프라이버시 비용이 $T$에 대해 로그 스케일인 $O(\sqrt{d}\,\log T/\sqrt{ρ})$에 불과함을 증명한다. 또한, 엄격한 프라이버시 예산에서 유효 노이즈를 줄일 수 있는 푸아송 서브샘플링을 통한 프라이버시 증폭을 탐구한다. 합성 및 실세계 데이터셋에 대한 실험 결과는 다음을 보여준다. (1) AdaPrivate-TS는 $\varepsilon \in [0.5, 5]$에서 비공개 성능의 93-99%를 달성하며, UCB 대비 0.5-3.7%, 극단적인 $\varepsilon$에서 적응형 탐험 튜닝 시 최대 18%까지 성능을 능가한다. (2) 프라이버시 증폭은 낮은 $\varepsilon$에서 추가적으로 2-5%의 성능 향상을 제공한다. (3) MovieLens 및 Jester에서 AdaPrivate-TS는 이벤트 수준 기준 모델 중 전반적으로 최고 성능을 달성하며 $\varepsilon \geq 2$에서 지배적이다. (4) DP-SVD 비공개 특징 하에서 UCB 대비 Thompson Sampling의 우위가 +11%까지 증가하며, 이는 노이즈-불확실성 해석이 보상 프라이버시에만 국한되지 않음을 확인한다. 우리는 인터랙티브 zCDP 합성 하에서의 프라이버시 보장에 대한 엄밀한 증명과 수렴 곡선, 12-시드 신뢰구간, DP-SVD 특징 절제 실험을 포함한 포괄적인 평가를 제공한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.