論文の概要: Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback
- arxiv url: http://arxiv.org/abs/2502.04678v1
- Date: Fri, 07 Feb 2025 05:52:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-10 14:56:07.867965
- Title: Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback
- Title（参考訳）: 図形フィードバック付きクロスラーニングコンテキスト帯域の近距離境界
- Authors: Ruiyuan Huang, Zengfeng Huang,
- Abstract要約: グラフィカルフィードバックを用いたクロスラーニングの文脈的帯域幅問題に注目が集まっている。
鍵となる理論的問題は、$widetildeO(sqrtalpha T)$ regret のアルゴリズムが存在するかどうかである。
- 参考スコア（独自算出の注目度）: 17.43748116766233
- License:
- Abstract: The cross-learning contextual bandit problem with graphical feedback has recently attracted significant attention. In this setting, there is a contextual bandit with a feedback graph over the arms, and pulling an arm reveals the loss for all neighboring arms in the feedback graph across all contexts. Initially proposed by Han et al. (2024), this problem has broad applications in areas such as bidding in first price auctions, and explores a novel frontier in the feedback structure of bandit problems. A key theoretical question is whether an algorithm with $\widetilde{O}(\sqrt{\alpha T})$ regret exists, where $\alpha$ represents the independence number of the feedback graph. This question is particularly interesting because it concerns whether an algorithm can achieve a regret bound entirely independent of the number of contexts and matching the minimax regret of vanilla graphical bandits. Previous work has demonstrated that such an algorithm is impossible for adversarial contexts, but the question remains open for stochastic contexts. In this work, we affirmatively answer this open question by presenting an algorithm that achieves the minimax $\widetilde{O}(\sqrt{\alpha T})$ regret for cross-learning contextual bandits with graphical feedback and stochastic contexts. Notably, although that question is open even for stochastic bandits, we directly solve the strictly stronger adversarial bandit version of the problem.
- Abstract（参考訳）: グラフィカルフィードバックによるクロスラーニングの文脈的包帯問題は近年注目されている。
この設定では、腕にフィードバックグラフを持つコンテキスト的バンディットが存在し、腕を引っ張ると、すべてのコンテキストにまたがるフィードバックグラフ内のすべての隣の腕の損失が明らかになる。
最初はHan et al (2024) によって提案されたが、この問題は最初の価格オークションの入札などの分野に広く応用されており、バンディット問題のフィードバック構造における新たなフロンティアを探求している。
重要な理論的問題は、$\widetilde{O}(\sqrt{\alpha T})$ regret のアルゴリズムが存在するかどうかであり、$\alpha$はフィードバックグラフの独立数を表す。
この問題は特に興味深いのは、アルゴリズムがコンテキストの数に完全に依存していない後悔を達成できるかどうかを懸念し、バニラのグラフィカルな帯域幅に対するミニマックスの後悔と一致するためである。
従来の研究は、そのようなアルゴリズムは敵の文脈では不可能であることを示したが、その問題は確率的文脈では未解決のままである。
本稿では、このオープンな質問に対して、グラフィカルなフィードバックと確率的コンテキストを持つクロスラーニングのコンテキスト包帯に対して、 minimax $\widetilde{O}(\sqrt{\alpha T})$のアルゴリズムを提示することで、肯定的に答える。
特に、確率的バンディットに対してもその問題は開かれているが、この問題のより強い逆バンディットバージョンを直接解決する。
関連論文リスト
- Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳（メタデータ） (2024-09-09T18:23:07Z) - Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。
われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。
我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
論文 参考訳（メタデータ） (2024-04-09T04:45:18Z) - Stochastic contextual bandits with graph feedback: from independence number to MAS number [28.10186884181921]
グラフフィードバックによる文脈的帯域幅について検討する。
マルチアームのバンディット設定とは異なり、文脈的なバンディット設定では明らかにされていない。
我々は、コンテキストシーケンスやフィードバックグラフの重要なクラスに対して、ほぼ最適に後悔するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-02-12T06:56:13Z) - Optimal cross-learning for contextual bandits with unknown context
distributions [28.087360479901978]
本稿では,バルセイロ等のクロスラーニング環境において,文脈的包括的アルゴリズムを設計する際の問題点について考察する。
コンテクスト数によらずに$widetildeO(sqrtTK)$というほぼ厳密な(対数的要因まで)後悔境界を持つ効率的なアルゴリズムを提供する。
アルゴリズムのコアとなるのは,複数のエポックにまたがるアルゴリズムの実行をコーディネートする新しい手法である。
論文 参考訳（メタデータ） (2024-01-03T18:02:13Z) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear
Bandit Algorithms [39.70492757288025]
我々は,意思決定者がコンテキストを提供するコンテキスト線形帯域問題に対処する。
文脈問題を線形バンディット問題として解くことができることを示す。
この結果から,文脈的線形包帯に対して$O(dsqrtTlog T)$高確率残差が生じることが示唆された。
論文 参考訳（メタデータ） (2022-11-08T22:18:53Z) - Improved Algorithms for Bandit with Graph Feedback via Regret
Decomposition [2.3034251503343466]
グラフフィードバックによるバンディットの問題は、マルチアームバンディット(MAB)問題と専門家のアドバイスによる学習の両方を一般化する。
本稿では,フィードバックグラフの分割に基づく新しいアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2022-05-30T13:07:42Z) - Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文 参考訳（メタデータ） (2022-04-24T03:10:27Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。