論文の概要: Batched Bandits with Crowd Externalities
- arxiv url: http://arxiv.org/abs/2109.14733v1
- Date: Wed, 29 Sep 2021 21:43:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-01 15:07:05.013124
- Title: Batched Bandits with Crowd Externalities
- Title（参考訳）: 群衆の外部性を考慮したバッチバンド
- Authors: Romain Laroche, Othmane Safsafi, Raphael Feraud, Nicolas Broutin
- Abstract要約: Batched Multi-Armed Bandits (BMAB) の新たな設定について述べる。
ポリシー更新のタイミングはBMABアルゴリズムによって制御されず、代わりに、textitcrowdと呼ばれる各バッチで受信されたデータの量は、過去のアームの選択に影響される。
- 参考スコア（独自算出の注目度）: 11.876737078654976
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In Batched Multi-Armed Bandits (BMAB), the policy is not allowed to be
updated at each time step. Usually, the setting asserts a maximum number of
allowed policy updates and the algorithm schedules them so that to minimize the
expected regret. In this paper, we describe a novel setting for BMAB, with the
following twist: the timing of the policy update is not controlled by the BMAB
algorithm, but instead the amount of data received during each batch, called
\textit{crowd}, is influenced by the past selection of arms. We first design a
near-optimal policy with approximate knowledge of the parameters that we prove
to have a regret in $\mathcal{O}(\sqrt{\frac{\ln x}{x}}+\epsilon)$ where $x$ is
the size of the crowd and $\epsilon$ is the parameter error. Next, we implement
a UCB-inspired algorithm that guarantees an additional regret in
$\mathcal{O}\left(\max(K\ln T,\sqrt{T\ln T})\right)$, where $K$ is the number
of arms and $T$ is the horizon.
- Abstract（参考訳）: Batched Multi-Armed Bandits (BMAB) では、各ステップごとにポリシーを更新することはできない。
通常、設定は許容されるポリシー更新の最大数を主張し、アルゴリズムは期待される後悔を最小限に抑えるためにそれらをスケジュールする。
本稿では,BMABアルゴリズムによってポリシー更新のタイミングが制御されるのではなく,各バッチで受信されるデータ量である「textit{crowd}」が,過去のアーム選択の影響を受けていることを示す。
まず、パラメータの近似知識を持つ近似最適に近いポリシーを設計し、ここで$x$が群衆のサイズであり$\epsilon$がパラメータエラーであるような$\mathcal{o}(\sqrt{\frac{\ln x}{x}}+\epsilon)$で後悔することを証明します。
次に、UCBにインスパイアされたアルゴリズムを実装し、$\mathcal{O}\left(\max(K\ln T,\sqrt{T\ln T})\right)$でさらなる後悔を保証する。
関連論文リスト
- Generalized Linear Bandits with Limited Adaptivity [12.112051468737596]
限定適応性の制約内における一般化線形文脈帯域問題について検討する。
我々は2つのアルゴリズム, $textttB-GLinCB$ と $textttRS-GLinCB$ を提示した。
論文 参考訳（メタデータ） (2024-04-10T08:47:57Z) - MNL-Bandit in non-stationary environments [2.7737587389928793]
我々は,最悪の場合,$tildeOleft(min left sqrtNTL;,; Nfrac13(Delta_inftyK)frac13 Tfrac23 + sqrtNTrightright)$を後悔するアルゴリズムを提案する。
特に、非定常性による推定器に導入されたバイアスの厳密な評価を行い、新しい濃度境界を導出する。
論文 参考訳（メタデータ） (2023-03-04T21:10:42Z) - Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文 参考訳（メタデータ） (2022-04-24T03:10:27Z) - Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。
この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文 参考訳（メタデータ） (2022-03-24T08:14:12Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays [21.94728545221709]
制限のないフィードバック遅延を伴うMAB(Scale-Free Adversarial Multi Armed Bandit)問題を考える。
textttSFBankerは$mathcal O(sqrtK(D+T)L)cdot rm polylog(T, L)$ total regret, where $T$ is the total number of steps, $D$ is the total feedback delay。
論文 参考訳（メタデータ） (2021-10-26T04:06:51Z) - Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
論文 参考訳（メタデータ） (2021-09-29T14:07:21Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - (Locally) Differentially Private Combinatorial Semi-Bandits [26.462686161971803]
我々は,従来のマルチアーマッド・バンド(MAB)の拡張であるコンビニアル・セミバンド(CSB)と,より強力なローカル・ディファレンシャル・プライバシ(LDP)設定について検討した。
論文 参考訳（メタデータ） (2020-06-01T04:23:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。