論文の概要: Multi-armed Bandit Learning on a Graph
- arxiv url: http://arxiv.org/abs/2209.09419v1
- Date: Tue, 20 Sep 2022 02:31:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-21 17:25:49.624626
- Title: Multi-armed Bandit Learning on a Graph
- Title（参考訳）: グラフを用いたマルチアームバンディット学習
- Authors: Tianpeng Zhang (1), Kasper Johansson (2), Na Li (1)((1) Harvard
University, (2) KTH Royal Institute of Technology)
- Abstract要約: そこでは,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化するために,MABの拡張であるグラフバンディット(Graph bandit)について検討する。
我々は,楽観主義の原理を用いて長期探査・探索のバランスをとるオンライン学習アルゴリズムを設計する。
提案アルゴリズムは,ノード数として$O(|S|sqrtTlog(T)+D|S|log T)$Learning regret,ここでは$|S|$がノード数で$D$がグラフの直径であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The multi-armed bandit(MAB) problem is a simple yet powerful framework that
has been extensively studied in the context of decision-making under
uncertainty. In many real-world applications, such as robotic applications,
selecting an arm corresponds to a physical action that constrains the choices
of the next available arms (actions). Motivated by this, we study an extension
of MAB called the graph bandit, where an agent travels over a graph trying to
maximize the reward collected from different nodes. The graph defines the
freedom of the agent in selecting the next available nodes at each step. We
assume the graph structure is fully available, but the reward distributions are
unknown. Built upon an offline graph-based planning algorithm and the principle
of optimism, we design an online learning algorithm that balances long-term
exploration-exploitation using the principle of optimism. We show that our
proposed algorithm achieves $O(|S|\sqrt{T}\log(T)+D|S|\log T)$ learning regret,
where $|S|$ is the number of nodes and $D$ is the diameter of the graph, which
is superior compared to the best-known reinforcement learning algorithms under
similar settings. Numerical experiments confirm that our algorithm outperforms
several benchmarks. Finally, we present a synthetic robotic application modeled
by the graph bandit framework, where a robot moves on a network of
rural/suburban locations to provide high-speed internet access using our
proposed algorithm.
- Abstract（参考訳）: マルチアーム・バンディット(MAB)問題は単純だが強力なフレームワークであり、不確実性の下での意思決定の文脈で広く研究されている。
ロボットアプリケーションのような現実世界の多くのアプリケーションでは、アームの選択は、次の利用可能なアーム(アクション)の選択を制限する物理的なアクションに対応する。
そこで我々は,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化しようとするグラフバンディットと呼ばれるMABの拡張について検討する。
グラフは各ステップで次の利用可能なノードを選択する際のエージェントの自由を定義する。
グラフ構造が完全に利用可能であると仮定するが、報酬分布は不明である。
オフライングラフベースの計画アルゴリズムと楽観主義の原理に基づいて構築され、楽観主義の原理を用いて長期探索・探索のバランスをとるオンライン学習アルゴリズムを設計する。
提案手法は, ノード数を$|s|$, グラフの直径を$d$とし, 類似条件下では最もよく知られた強化学習アルゴリズムよりも優れる$o(|s|\sqrt{t}\log(t)+d|s|\log t)$学習後悔を実現する。
数値実験により,本アルゴリズムはいくつかのベンチマークより優れていることを確認した。
最後に,都市部や郊外のネットワーク上でロボットが移動して,提案アルゴリズムを用いて高速なインターネットアクセスを実現するための,グラフバンディットフレームワークをモデルとした合成ロボットアプリケーションを提案する。
関連論文リスト
- Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。
この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。
我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-02-27T18:12:58Z) - Stochastic contextual bandits with graph feedback: from independence number to MAS number [28.10186884181921]
グラフフィードバックによる文脈的帯域幅について検討する。
マルチアームのバンディット設定とは異なり、文脈的なバンディット設定では明らかにされていない。
我々は、コンテキストシーケンスやフィードバックグラフの重要なクラスに対して、ほぼ最適に後悔するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-02-12T06:56:13Z) - 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) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳（メタデータ） (2022-07-13T18:12:36Z) - Simultaneously Learning Stochastic and Adversarial Bandits with General
Graph Feedback [15.429356827868514]
一般フィードバックグラフの探索と活用のための新たなトレードオフ機構を導入する。
提案アルゴリズムは,対数設定において,$mathrmpoly-designed log T$ regretを同時に達成する。
これは、一般のフィードバックグラフに対する世界で初めての最良の結果である。
論文 参考訳（メタデータ） (2022-06-16T04:21:27Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - Node Feature Extraction by Self-Supervised Multi-scale Neighborhood
Prediction [123.20238648121445]
我々は、新しい自己教師型学習フレームワーク、グラフ情報支援ノード機能exTraction (GIANT)を提案する。
GIANT は eXtreme Multi-label Classification (XMC) 形式を利用しており、これはグラフ情報に基づいた言語モデルの微調整に不可欠である。
我々は,Open Graph Benchmarkデータセット上での標準GNNパイプラインよりもGIANTの方が優れた性能を示す。
論文 参考訳（メタデータ） (2021-10-29T19:55:12Z) - Causal Bandits on General Graphs [1.4502611532302039]
本稿では、因果グラフのみによって指定された因果ベイズネットワーク(CBN)における最良の介入を決定する問題について検討する。
本稿では,原子間干渉や観測不可能な変数を含む半マルコフ因果グラフを入力として用いた,簡単な後悔最小化アルゴリズムを提案する。
この結果から,提案アルゴリズムの単純後悔保証は,因果グラフのより微妙な構造的制約を考慮すれば改善できることがわかった。
論文 参考訳（メタデータ） (2021-07-06T17:29:45Z) - Learnable Graph Matching: Incorporating Graph Partitioning with Deep
Feature Learning for Multiple Object Tracking [58.30147362745852]
フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。
既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。
そこで本研究では,学習可能なグラフマッチング手法を提案する。
論文 参考訳（メタデータ） (2021-03-30T08:58:45Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。