論文の概要: Optimal cross-learning for contextual bandits with unknown context distributions

• arxiv url: http://arxiv.org/abs/2401.01857v1
• Date: Wed, 3 Jan 2024 18:02:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-04 13:22:09.022891
• Title: Optimal cross-learning for contextual bandits with unknown context distributions
• Title（参考訳）: 未知文脈分布をもつコンテキストバンディットの最適クロスラーニング
• Authors: Jon Schneider, Julian Zimmert
• Abstract要約: 本稿では,バルセイロ等のクロスラーニング環境において,文脈的包括的アルゴリズムを設計する際の問題点について考察する。 コンテクスト数によらずに$widetildeO(sqrtTK)$というほぼ厳密な(対数的要因まで)後悔境界を持つ効率的なアルゴリズムを提供する。 アルゴリズムのコアとなるのは,複数のエポックにまたがるアルゴリズムの実行をコーディネートする新しい手法である。
• 参考スコア（独自算出の注目度）: 28.087360479901978
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of designing contextual bandit algorithms in the ``cross-learning'' setting of Balseiro et al., where the learner observes the loss for the action they play in all possible contexts, not just the context of the current round. We specifically consider the setting where losses are chosen adversarially and contexts are sampled i.i.d. from an unknown distribution. In this setting, we resolve an open problem of Balseiro et al. by providing an efficient algorithm with a nearly tight (up to logarithmic factors) regret bound of $\widetilde{O}(\sqrt{TK})$, independent of the number of contexts. As a consequence, we obtain the first nearly tight regret bounds for the problems of learning to bid in first-price auctions (under unknown value distributions) and sleeping bandits with a stochastic action set. At the core of our algorithm is a novel technique for coordinating the execution of a learning algorithm over multiple epochs in such a way to remove correlations between estimation of the unknown distribution and the actions played by the algorithm. This technique may be of independent interest for other learning problems involving estimation of an unknown context distribution.
• Abstract（参考訳）: 本稿では,学習者が現在ラウンドのコンテキストだけでなく,可能なすべてのコンテキストで行う行動の損失を観察するバルセイロ等の「クロスラーニング」設定における文脈的バンディットアルゴリズムの設計問題を考察する。 具体的には,損失が敵対的に選択され,文脈が未知の分布からサンプリングされる状況について考察する。 この設定では、コンテキストの個数とは無関係に$\widetilde{O}(\sqrt{TK})$の後悔境界をほぼ緊密に(対数的因子まで)持つ効率的なアルゴリズムを提供することで、バルセイロらのオープンな問題を解く。 その結果、初値オークション(未知値分布)や睡眠バンディットに確率的行動セットで入札する学習の問題に対する、最初の厳密な後悔の限界を得ることができた。 本アルゴリズムのコアとなるのは,未知分布の推定とアルゴリズムが実行する動作との相関を除去する手段として,複数のエポックにまたがる学習アルゴリズムの実行をコーディネートする新しい手法である。 この手法は、未知の文脈分布の推定を含む他の学習問題に対して独立した関心を持つ可能性がある。

関連論文リスト

• High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions [17.43748116766233]
  クロスラーニング(クロスラーニング)による文脈的包帯の問題について検討し、学習者はあらゆる可能な文脈で行動に関連した損失を観察する。 我々の焦点は、損失が逆向きに選択され、特定の分布からコンテキストがサンプル化されるような設定である。 Schneider と Zimmert (2023) は先頃、ほぼ最適に期待された後悔を実現するアルゴリズムを提案した。 提案手法は,そのアルゴリズムの詳細な解析を行い,ほぼ最適の後悔を高い確率で実現できることを実証する。
  論文  参考訳（メタデータ） (2024-10-05T08:19:54Z)
• Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
  FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。 われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。 我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
  論文  参考訳（メタデータ） (2024-04-09T04:45:18Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Online learning in bandits with predicted context [8.257280652461159]
  エージェントがコンテキストの騒々しいバージョンにしかアクセスできない場合、コンテキスト的帯域幅の問題を考える。 この設定は、意思決定の真のコンテキストが守られない広範囲のアプリケーションによって動機付けられている。 本研究では,この設定において,軽度条件下でのサブ線形後悔保証を用いた最初のオンラインアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-26T02:33:54Z)
• Distributed Stochastic Bandit Learning with Context Distributions [0.0]
  本研究では,未知のコンテキストを持つ分散マルチアームコンテキスト帯域幅の問題について検討する。 本モデルでは, エージェントはコンテキスト分布のみを観察し, エージェントに正確なコンテキストが不明である。 我々のゴールは、累積報酬を最大化するために最適な行動列を選択する分散アルゴリズムを開発することである。
  論文  参考訳（メタデータ） (2022-07-28T22:00:11Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。 我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
  論文  参考訳（メタデータ） (2020-05-18T08:41:39Z)
• Contextual Blocking Bandits [35.235375147227124]
  我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。 アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。 我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
  論文  参考訳（メタデータ） (2020-03-06T20:34:42Z)
• Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
  我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。 提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-20T06:36:19Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。