論文の概要: On the Optimal Regret of Locally Private Linear Contextual Bandit
- arxiv url: http://arxiv.org/abs/2404.09413v1
- Date: Mon, 15 Apr 2024 02:00:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-16 13:58:36.050135
- Title: On the Optimal Regret of Locally Private Linear Contextual Bandit
- Title(参考訳): 局所プライベート線形帯域の最適レグレットについて
- Authors: Jiachun Li, David Simchi-Levi, Yining Wang,
- Abstract要約: 局所的なプライベートな文脈的帯域に対して,$tilde O(sqrtT)$ regret upper bound を達成可能であることを示す。
我々の解決策は、いくつかの新しいアルゴリズム的および分析的アイデアに依存している。
- 参考スコア(独自算出の注目度): 18.300225068036642
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Contextual bandit with linear reward functions is among one of the most extensively studied models in bandit and online learning research. Recently, there has been increasing interest in designing \emph{locally private} linear contextual bandit algorithms, where sensitive information contained in contexts and rewards is protected against leakage to the general public. While the classical linear contextual bandit algorithm admits cumulative regret upper bounds of $\tilde O(\sqrt{T})$ via multiple alternative methods, it has remained open whether such regret bounds are attainable in the presence of local privacy constraints, with the state-of-the-art result being $\tilde O(T^{3/4})$. In this paper, we show that it is indeed possible to achieve an $\tilde O(\sqrt{T})$ regret upper bound for locally private linear contextual bandit. Our solution relies on several new algorithmic and analytical ideas, such as the analysis of mean absolute deviation errors and layered principal component regression in order to achieve small mean absolute deviation errors.
- Abstract(参考訳): 線形報酬関数を持つ文脈的バンディットは、バンディットとオンライン学習研究において最も広く研究されているモデルの1つである。
近年、文脈や報酬に含まれるセンシティブな情報を一般大衆に漏えいから保護する「emph{locally private} linear contextual bandit algorithm」の設計への関心が高まっている。
古典的線形文脈的帯域幅アルゴリズムは、複数の代替手法を介して$\tilde O(\sqrt{T})$の累積後悔上限を許容するが、そのような後悔境界が局所的なプライバシー制約の存在下で達成可能かどうかについては未定のままであり、その結果は$\tilde O(T^{3/4})$である。
本稿では,局所的線形文脈帯域に対して,$\tilde O(\sqrt{T})$ regret upper bound を実現することができることを示す。
我々の解は、平均絶対偏差誤差の解析や、最小平均偏差誤差を達成するための階層化された主成分回帰など、いくつかの新しいアルゴリズム的および解析的アイデアに依存している。
関連論文リスト
- Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。
本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
論文 参考訳(メタデータ) (2023-10-02T19:59:39Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-19T01:09:24Z) - Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear
Contextual Bandits and Markov Decision Processes [59.61248760134937]
本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。
提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。
本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
論文 参考訳(メタデータ) (2022-12-12T15:04:56Z) - Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear
Bandit Algorithms [39.70492757288025]
我々は,意思決定者がコンテキストを提供するコンテキスト線形帯域問題に対処する。
文脈問題を線形バンディット問題として解くことができることを示す。
この結果から,文脈的線形包帯に対して$O(dsqrtTlog T)$高確率残差が生じることが示唆された。
論文 参考訳(メタデータ) (2022-11-08T22:18:53Z) - On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。
本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。
本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳(メタデータ) (2022-03-29T14:02:03Z) - Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。
楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。
我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
論文 参考訳(メタデータ) (2021-10-21T15:25:15Z) - High-Dimensional Sparse Linear Bandits [67.9378546011416]
データ・ポーア・システマティクスにおける疎線形包帯に対して、新しい$Omega(n2/3)$ dimension-free minimax regret lower boundを導出する。
また、関連する特徴に対する信号の大きさに関する追加の仮定の下で、次元のない$O(sqrtn)$ regret上界も証明する。
論文 参考訳(メタデータ) (2020-11-08T16:48:11Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳(メタデータ) (2020-09-04T04:10:39Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。