論文の概要: Stochastic contextual bandits with graph feedback: from independence number to MAS number

• arxiv url: http://arxiv.org/abs/2402.18591v2
• Date: Wed, 06 Nov 2024 19:40:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-08 19:35:30.816073
• Title: Stochastic contextual bandits with graph feedback: from independence number to MAS number
• Title（参考訳）: グラフフィードバックによる確率的文脈帯域幅:独立数からMAS数へ
• Authors: Yuxiao Wen, Yanjun Han, Zhengyuan Zhou,
• Abstract要約: グラフフィードバックによる文脈的帯域幅について検討する。 マルチアームのバンディット設定とは異なり、文脈的なバンディット設定では明らかにされていない。 我々は、コンテキストシーケンスやフィードバックグラフの重要なクラスに対して、ほぼ最適に後悔するアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 28.10186884181921
• License:
• Abstract: We consider contextual bandits with graph feedback, a class of interactive learning problems with richer structures than vanilla contextual bandits, where taking an action reveals the rewards for all neighboring actions in the feedback graph under all contexts. Unlike the multi-armed bandits setting where a growing literature has painted a near-complete understanding of graph feedback, much remains unexplored in the contextual bandits counterpart. In this paper, we make inroads into this inquiry by establishing a regret lower bound $\Omega(\sqrt{\beta_M(G) T})$, where $M$ is the number of contexts, $G$ is the feedback graph, and $\beta_M(G)$ is our proposed graph-theoretic quantity that characterizes the fundamental learning limit for this class of problems. Interestingly, $\beta_M(G)$ interpolates between $\alpha(G)$ (the independence number of the graph) and $\mathsf{m}(G)$ (the maximum acyclic subgraph (MAS) number of the graph) as the number of contexts $M$ varies. We also provide algorithms that achieve near-optimal regret for important classes of context sequences and/or feedback graphs, such as transitively closed graphs that find applications in auctions and inventory control. In particular, with many contexts, our results show that the MAS number essentially characterizes the statistical complexity for contextual bandits, as opposed to the independence number in multi-armed bandits.
• Abstract（参考訳）: グラフフィードバックを用いた文脈的帯域幅は、バニラの文脈的帯域幅よりもリッチな構造を持つ対話的学習問題であり、任意のコンテキスト下でのすべての隣り合う行動に対する報酬を明らかにする。 成長する文献がグラフフィードバックのほぼ完全な理解を描いているマルチアームのバンディット設定とは異なり、文脈的なバンディットとは相容れない。 ここでは、M$は文脈の数、G$はフィードバックグラフ、そして$\beta_M(G)$は、この問題のクラスの基本学習限界を特徴づけるグラフ理論量である。 興味深いことに、$\beta_M(G)$は$\alpha(G)$(グラフの独立数)と$\mathsf{m}(G)$(グラフの最大非巡回部分グラフ(MAS)数)の間の補間を行う。 また、オークションや在庫管理の応用を見出す推移的に閉じたグラフなど、コンテキストシーケンスや/またはフィードバックグラフの重要なクラスに対して、ほぼ最適に後悔するアルゴリズムも提供する。 特に,多くの文脈において,MAS数は,マルチアームバンディットの独立数とは対照的に,文脈的バンディットの統計的複雑性を本質的に特徴付けることを示す。

関連論文リスト

• Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
  Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。 本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
  論文  参考訳（メタデータ） (2024-09-09T18:23:07Z)
• G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering [61.93058781222079]
  現実のテキストグラフを対象とするフレキシブルな問合せフレームワークを開発した。 一般のテキストグラフに対する最初の検索拡張生成(RAG)手法を提案する。 G-Retrieverは、このタスクをSteiner Tree最適化問題として定式化し、グラフ上でRAGを実行する。
  論文  参考訳（メタデータ） (2024-02-12T13:13:04Z)
• Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
  ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。 複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
  論文  参考訳（メタデータ） (2023-06-05T15:35:00Z)
• Stochastic Contextual Bandits with Graph-based Contexts [0.0]
  オンライングラフ予測問題を文脈的帯域問題に一般化する。 我々のアルゴリズムは Zimmert と Seldin[AISTAT'19, JMLR'21] による最適帯域幅アルゴリズムに依存している。
  論文  参考訳（メタデータ） (2023-05-02T14:51:35Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Multi-armed Bandit Learning on a Graph [0.0]
  そこで,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化するグラフバンドイットと呼ばれるMABの拡張について検討する。 我々は,楽観主義の原理を用いて長期探査・探索のバランスをとる学習アルゴリズムG-UCBを設計する。 提案アルゴリズムは,ノード数として$O(sqrt|S|Tlog(T)+D|S|log T)$学習後悔を実現する。
  論文  参考訳（メタデータ） (2022-09-20T02:31:42Z)
• Improved Algorithms for Bandit with Graph Feedback via Regret Decomposition [2.3034251503343466]
  グラフフィードバックによるバンディットの問題は、マルチアームバンディット(MAB)問題と専門家のアドバイスによる学習の両方を一般化する。 本稿では,フィードバックグラフの分割に基づく新しいアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-05-30T13:07:42Z)
• Beyond Bandit Feedback in Online Multiclass Classification [17.07011090727996]
  学習者のフィードバックが任意の有向グラフによって決定されるような環境で,オンライン多クラス分類の問題について検討する。 任意のフィードバックグラフで動作する,初のオンラインマルチクラスアルゴリズムであるGappletronを紹介する。
  論文  参考訳（メタデータ） (2021-06-07T13:22:30Z)
• 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)

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

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