論文の概要: Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations
- arxiv url: http://arxiv.org/abs/2012.05756v3
- Date: Wed, 17 Feb 2021 01:58:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-15 06:17:05.588671
- Title: Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations
- Title（参考訳）: グラフ構造側観察による逆線形コンテキスト帯域
- Authors: Lingda Wang, Bingcong Li, Huozhi Zhou, Georgios B. Giannakis, Lav R.
Varshney, Zhizhen Zhao
- Abstract要約: 学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
- 参考スコア（独自算出の注目度）: 80.95090605985042
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the adversarial graphical contextual bandits, a variant of
adversarial multi-armed bandits that leverage two categories of the most common
side information: \emph{contexts} and \emph{side observations}. In this
setting, a learning agent repeatedly chooses from a set of $K$ actions after
being presented with a $d$-dimensional context vector. The agent not only
incurs and observes the loss of the chosen action, but also observes the losses
of its neighboring actions in the observation structures, which are encoded as
a series of feedback graphs. This setting models a variety of applications in
social networks, where both contexts and graph-structured side observations are
available. Two efficient algorithms are developed based on \texttt{EXP3}. Under
mild conditions, our analysis shows that for undirected feedback graphs the
first algorithm, \texttt{EXP3-LGC-U}, achieves the regret of order
$\mathcal{O}(\sqrt{(K+\alpha(G)d)T\log{K}})$ over the time horizon $T$, where
$\alpha(G)$ is the average \emph{independence number} of the feedback graphs. A
slightly weaker result is presented for the directed graph setting as well. The
second algorithm, \texttt{EXP3-LGC-IX}, is developed for a special class of
problems, for which the regret is reduced to
$\mathcal{O}(\sqrt{\alpha(G)dT\log{K}\log(KT)})$ for both directed as well as
undirected feedback graphs. Numerical tests corroborate the efficiency of
proposed algorithms.
- Abstract（参考訳）: 本稿では,最も一般的な側面情報である \emph{contexts} と \emph{side observed} の2つのカテゴリを利用する,対角的多腕包帯の変種である,対角的背景包帯について検討する。
この設定において、学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を発生させ、観察するだけでなく、一連のフィードバックグラフとして符号化された観測構造における隣り合うアクションの損失も観察する。
この設定は、コンテキストとグラフ構造化された側観察の両方が利用できるソーシャルネットワークの様々なアプリケーションをモデル化する。
2つの効率的なアルゴリズムが \texttt{EXP3} に基づいて開発された。
軽度条件下では、無方向性フィードバックグラフに対して、最初のアルゴリズムである \texttt{EXP3-LGC-U} が次数$\mathcal{O}(\sqrt{(K+\alpha(G)d)T\log{K}})$オーバーザタイム水平線$T$, ここで、$\alpha(G)$はフィードバックグラフの平均 \emph{independence number} となる。
有向グラフの設定についても、もう少し弱い結果が示されます。
第2のアルゴリズムである \textt{exp3-lgc-ix} は特別な問題のクラスのために開発され、後悔は有向および無向フィードバックグラフに対して$\mathcal{o}(\sqrt{\alpha(g)dt\log{k}\log(kt)})$となる。
数値実験は提案アルゴリズムの効率を相関させる。
関連論文リスト
- 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) - Simultaneously Learning Stochastic and Adversarial Bandits with General
Graph Feedback [15.429356827868514]
一般フィードバックグラフの探索と活用のための新たなトレードオフ機構を導入する。
提案アルゴリズムは,対数設定において,$mathrmpoly-designed log T$ regretを同時に達成する。
これは、一般のフィードバックグラフに対する世界で初めての最良の結果である。
論文 参考訳（メタデータ） (2022-06-16T04:21:27Z) - Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with
Feedback Graphs [34.37963000493442]
本研究では,汎用的なフィードバックグラフを用いたオンライン学習について考察する。
両世界のベスト・オブ・ワールドズ・アルゴリズムは、敵の環境に対してほぼ厳密な後悔の限界を達成できる。
論文 参考訳（メタデータ） (2022-06-02T05:01:40Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
本稿では,グラフマッチングを向上するための信頼度の高いグラフ構造を探索するために,GLAMという共用電子グラフ学習とマッチングネットワークを提案する。
提案手法は,3つの人気ビジュアルマッチングベンチマーク (Pascal VOC, Willow Object, SPair-71k) で評価される。
すべてのベンチマークにおいて、従来の最先端のグラフマッチング手法よりも大きなマージンを達成している。
論文 参考訳（メタデータ） (2021-09-01T08:24:02Z) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。
我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。
これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文 参考訳（メタデータ） (2021-01-28T02:39:27Z) - Dual ResGCN for Balanced Scene GraphGeneration [106.7828712878278]
本稿では,オブジェクト残差グラフ畳み込みネットワークと関係残差グラフ畳み込みネットワークからなる新しいモデルであるtextitdual ResGCNを提案する。
2つのネットワークは相互に補完的であり、前者はオブジェクトレベルのコンテキスト情報、すなわちオブジェクト間の接続をキャプチャする。
後者は、関係レベルのコンテキスト情報、すなわち関係間の関係を明示的にキャプチャするように設計されている。
論文 参考訳（メタデータ） (2020-11-09T07:44:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。