論文の概要: Bandits with Stochastic Experts: Constant Regret, Empirical Experts and Episodes
- arxiv url: http://arxiv.org/abs/2107.03263v3
- Date: Mon, 28 Oct 2024 00:58:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-30 20:19:50.880335
- Title: Bandits with Stochastic Experts: Constant Regret, Empirical Experts and Episodes
- Title（参考訳）: 確率的専門家とのバンド: 一定の規則、経験的専門家、エピソード
- Authors: Nihal Sharma, Rajat Sen, Soumya Basu, Karthikeyan Shanmugam, Sanjay Shakkottai,
- Abstract要約: エージェントが一連の専門家ポリシーを介し介入できる文脈的帯域幅問題の変種について検討する。
本稿では,D-UCB(Divergence-based Upper Confidence Bound)アルゴリズムを提案する。
また,経験的D-UCB (ED-UCB) アルゴリズムも提案する。
- 参考スコア（独自算出の注目度）: 36.104981594178525
- License:
- Abstract: We study a variant of the contextual bandit problem where an agent can intervene through a set of stochastic expert policies. Given a fixed context, each expert samples actions from a fixed conditional distribution. The agent seeks to remain competitive with the 'best' among the given set of experts. We propose the Divergence-based Upper Confidence Bound (D-UCB) algorithm that uses importance sampling to share information across experts and provide horizon-independent constant regret bounds that only scale linearly in the number of experts. We also provide the Empirical D-UCB (ED-UCB) algorithm that can function with only approximate knowledge of expert distributions. Further, we investigate the episodic setting where the agent interacts with an environment that changes over episodes. Each episode can have different context and reward distributions resulting in the best expert changing across episodes. We show that by bootstrapping from $\mathcal{O}\left(N\log\left(NT^2\sqrt{E}\right)\right)$ samples, ED-UCB guarantees a regret that scales as $\mathcal{O}\left(E(N+1) + \frac{N\sqrt{E}}{T^2}\right)$ for $N$ experts over $E$ episodes, each of length $T$. We finally empirically validate our findings through simulations.
- Abstract（参考訳）: エージェントが確率的専門家ポリシーの集合を通して介入できる文脈的包帯問題の変種について検討する。
固定されたコンテキストを与えられた各専門家は、固定された条件分布からアクションをサンプリングする。
エージェントは、与えられた専門家のセットの中で「ベスト」と競争し続けることを目指している。
本稿では,D-UCBアルゴリズムを提案する。D-UCBアルゴリズムは,重要サンプリングを用いて専門家間で情報を共有し,専門家数にのみ線形にスケールする水平非依存な連続後悔境界を提供する。
また,経験的D-UCB (ED-UCB) アルゴリズムも提案する。
さらに、エージェントがエピソードによって変化する環境と相互作用するエピソード設定について検討する。
各エピソードは異なる文脈と報酬分布を持つことができ、その結果、エピソード毎に最も優れた専門家が変化する。
ED-UCBは、$\mathcal{O}\left(N\log\left(NT^2\sqrt{E}\right)\right)$サンプルからブートストラップすることで、$\mathcal{O}\left(E(N+1) + \frac{N\sqrt{E}}{T^2}\right)$に対して$E$のエピソードに対して$N$の専門家に対して$T$の後悔を保証する。
最終的に、シミュレーションを通して、我々の発見を実証的に検証した。
関連論文リスト
- Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
我々は、dタスクのパフォーマンスに基づいて、n名のエキスパートをランク付けする問題を考察する。
我々は,各専門家のペアに対して,各タスクにおいて他方よりも優れているという,単調な仮定を定めている。
論文 参考訳（メタデータ） (2023-06-05T06:55:39Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳（メタデータ） (2023-01-31T03:49:00Z) - Tractable Optimality in Episodic Latent MABs [75.17357040707347]
我々は、エージェントが時間ステップ$H$のエピソードのために環境と対話する、M$遅延コンテキストを持つマルチアームバンディット問題を考える。
エピソードの長さによっては、学習者は遅れた文脈を正確に見積もることができないかもしれない。
我々は、$O(textttpoly(A) + textttpoly(M,H)min(M,H))$インタラクションを用いて、ほぼ最適なポリシーを確実に学習する手順を設計する。
論文 参考訳（メタデータ） (2022-10-05T22:53:46Z) - Balanced Product of Calibrated Experts for Long-Tailed Recognition [13.194151879344487]
多くの実世界の認識問題は長いラベルの分布によって特徴づけられる。
本研究では分析的アプローチを採り、ロジット調整の概念をアンサンブルに拡張し、専門家のバランス製品(BalPoE)を形成する。
我々はこれらの分布を適切に定義し、偏りのない予測を達成するために専門家を組み合わせる方法を示す。
論文 参考訳（メタデータ） (2022-06-10T17:59:02Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳（メタデータ） (2022-06-07T18:08:21Z) - Nonstochastic Bandits with Infinitely Many Experts [1.7188280334580197]
無限に多くの専門家と非確率的盗賊の問題を考察する。
有限個の専門家に対して、正しい専門家ランキングの推測を可能にするExp4.Pの変種を提案する。
そして、この変種を無限に多くの専門家に作用するメタアルゴリズムに組み込む。
論文 参考訳（メタデータ） (2021-02-09T22:42:36Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Simultaneously Learning Stochastic and Adversarial Episodic MDPs with
Known Transition [38.28925339231888]
我々は,世界最良保証付きの最初のアルゴリズムを開発した。
損失が逆ならば、$mathcalO(log T)$ regretを達成します。
より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
論文 参考訳（メタデータ） (2020-06-10T01:59:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。