論文の概要: High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
- arxiv url: http://arxiv.org/abs/2410.04080v1
- Date: Sat, 5 Oct 2024 08:19:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 14:20:57.457310
- Title: High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions
- Title（参考訳）: 未知のコンテキスト分布を持つクロスラーニングコンテキスト帯域に対する高確率境界
- Authors: Ruiyuan Huang, Zengfeng Huang,
- Abstract要約: クロスラーニング(クロスラーニング)による文脈的包帯の問題について検討し、学習者はあらゆる可能な文脈で行動に関連した損失を観察する。
我々の焦点は、損失が逆向きに選択され、特定の分布からコンテキストがサンプル化されるような設定である。
Schneider と Zimmert (2023) は先頃、ほぼ最適に期待された後悔を実現するアルゴリズムを提案した。
提案手法は,そのアルゴリズムの詳細な解析を行い,ほぼ最適の後悔を高い確率で実現できることを実証する。
- 参考スコア（独自算出の注目度）: 17.43748116766233
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by applications in online bidding and sleeping bandits, we examine the problem of contextual bandits with cross learning, where the learner observes the loss associated with the action across all possible contexts, not just the current round's context. Our focus is on a setting where losses are chosen adversarially, and contexts are sampled i.i.d. from a specific distribution. This problem was first studied by Balseiro et al. (2019), who proposed an algorithm that achieves near-optimal regret under the assumption that the context distribution is known in advance. However, this assumption is often unrealistic. To address this issue, Schneider and Zimmert (2023) recently proposed a new algorithm that achieves nearly optimal expected regret. It is well-known that expected regret can be significantly weaker than high-probability bounds. In this paper, we present a novel, in-depth analysis of their algorithm and demonstrate that it actually achieves near-optimal regret with high probability. There are steps in the original analysis by Schneider and Zimmert (2023) that lead only to an expected bound by nature. In our analysis, we introduce several new insights. Specifically, we make extensive use of the weak dependency structure between different epochs, which was overlooked in previous analyses. Additionally, standard martingale inequalities are not directly applicable, so we refine martingale inequalities to complete our analysis.
- Abstract（参考訳）: オンライン入札や睡眠バンドイットの応用により、学習者が現在のラウンドのコンテキストだけでなく、あらゆる可能なコンテキストにおける行動に関連した損失を観察するクロスラーニングによるコンテキストバンドイットの問題を検討する。
我々の焦点は、損失が逆向きに選択され、特定の分布からコンテキストがサンプリングされるような設定である。
この問題を最初に研究したのは Balseiro et al (2019) で、彼は文脈分布が事前に知られているという仮定の下で、ほぼ最適に後悔するアルゴリズムを提案した。
しかし、この仮定はしばしば非現実的である。
この問題に対処するため、Schneider と Zimmert (2023) は先頃、ほぼ最適に期待された後悔を実現する新しいアルゴリズムを提案した。
期待された後悔は、高い確率境界よりも著しく弱いことが知られている。
本稿では,そのアルゴリズムの詳細な解析を行い,確率の高いほぼ最適の後悔を実際に達成できることを実証する。
シュナイダー (Schneider) とジマート (Zimmert) (2023) による最初の分析では、自然界にのみ到達している。
分析では、いくつかの新しい知見を紹介します。
具体的には,従来の分析では見過ごされなかった異なるエポック間の弱い依存関係構造を広範囲に利用した。
さらに、標準的なマーチンゲール不等式は直接適用されないので、分析を完了するためにマーチンゲール不等式を洗練する。
関連論文リスト
- Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood [28.94461817548213]
多元的文脈木への射影後のシュタルコフ和に対応する新しい複雑性測度であるエンフコンテクスチュアルシュタルコフ和を導入する。
emph Normalized Maximum Likelihood (cNML) と呼ばれるミニマックス最適戦略を導出する。
私たちの結果は、バイナリラベルを超えて、シーケンシャルな専門家に当てはまります。
論文 参考訳（メタデータ） (2024-10-04T18:31:12Z) - Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals [28.94461817548213]
条件付き良性環境と任意の環境下での学習性能におけるトレードオフの可能性について,上界と下界の整合性を証明した。
この問題を線形バンディット設定に還元することで、最初に因果バンディットのインスタンス依存境界を求める。
論文 参考訳（メタデータ） (2024-07-01T04:12:15Z) - Thompson Sampling in Partially Observable Contextual Bandits [2.465689259704613]
我々は、観測データに基づいて最適な腕を選択することを学ぶための盗賊政策について研究する。
我々の理論的分析は、トンプソンサンプリング政策が探索と搾取のバランスをうまくとれることを示している。
これらの技術は、文脈情報や部分的な観察とともに、他の意思決定問題の研究への道を開く。
論文 参考訳（メタデータ） (2024-02-15T19:37:39Z) - Optimal cross-learning for contextual bandits with unknown context
distributions [28.087360479901978]
本稿では,バルセイロ等のクロスラーニング環境において,文脈的包括的アルゴリズムを設計する際の問題点について考察する。
コンテクスト数によらずに$widetildeO(sqrtTK)$というほぼ厳密な(対数的要因まで)後悔境界を持つ効率的なアルゴリズムを提供する。
アルゴリズムのコアとなるのは,複数のエポックにまたがるアルゴリズムの実行をコーディネートする新しい手法である。
論文 参考訳（メタデータ） (2024-01-03T18:02:13Z) - 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) - Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear
Bandit Algorithms [39.70492757288025]
我々は,意思決定者がコンテキストを提供するコンテキスト線形帯域問題に対処する。
文脈問題を線形バンディット問題として解くことができることを示す。
この結果から,文脈的線形包帯に対して$O(dsqrtTlog T)$高確率残差が生じることが示唆された。
論文 参考訳（メタデータ） (2022-11-08T22:18:53Z) - A Unifying Theory of Thompson Sampling for Continuous Risk-Averse
Bandits [91.3755431537592]
本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。
大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。
リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
論文 参考訳（メタデータ） (2021-08-25T17:09:01Z) - A Low Rank Promoting Prior for Unsupervised Contrastive Learning [108.91406719395417]
提案手法は,従来の低階の促進をコントラスト学習の枠組みに効果的に組み込む新しい確率的グラフィカルモデルを構築する。
我々の仮説は、同じインスタンスクラスに属するすべてのサンプルが、小さな次元の同じ部分空間上にあることを明示的に要求する。
実証的な証拠は、提案アルゴリズムが複数のベンチマークにおける最先端のアプローチを明らかに上回っていることを示している。
論文 参考訳（メタデータ） (2021-08-05T15:58:25Z) - Efficient First-Order Contextual Bandits: Prediction, Allocation, and
Triangular Discrimination [82.52105963476703]
統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。
1次保証は統計的およびオンライン学習において比較的よく理解されている。
三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
論文 参考訳（メタデータ） (2021-07-05T19:20:34Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Latent Bandits Revisited [55.88616813182679]
潜伏盗賊問題は、学習エージェントが未知の離散潜伏状態に条件付けられた腕の報酬分布を知知する問題である。
本稿では, 上位信頼境界(UCB)とトンプソンサンプリング(Thompson sample)の両方に基づいて, この設定のための一般的なアルゴリズムを提案する。
我々はアルゴリズムの統一的な理論的解析を行い、遅延状態の数がアクションよりも小さい場合、古典的なバンディットポリシーよりも後悔度が低い。
論文 参考訳（メタデータ） (2020-06-15T19:24:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。