論文の概要: An $\alpha$-No-Regret Algorithm For Graphical Bilinear Bandits
- arxiv url: http://arxiv.org/abs/2206.00466v1
- Date: Wed, 1 Jun 2022 12:55:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-02 18:55:26.975774
- Title: An $\alpha$-No-Regret Algorithm For Graphical Bilinear Bandits
- Title（参考訳）: グラフィカル双線形帯域に対する$\alpha$-No-Regretアルゴリズム
- Authors: Geovani Rizk, Igor Colin, Albert Thomas, Rida Laraki, Yann Chevaleyre
- Abstract要約: 本稿では,グラフィカルビリニア帯域問題に対する最初の後悔に基づくアプローチを提案する。
本稿では,不確実性に直面した楽観主義の原理を用いて,バイリニアバンディットに対する最初の後悔に基づくアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 15.29268368415036
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose the first regret-based approach to the Graphical Bilinear Bandits
problem, where $n$ agents in a graph play a stochastic bilinear bandit game
with each of their neighbors. This setting reveals a combinatorial NP-hard
problem that prevents the use of any existing regret-based algorithm in the
(bi-)linear bandit literature. In this paper, we fill this gap and present the
first regret-based algorithm for graphical bilinear bandits using the principle
of optimism in the face of uncertainty. Theoretical analysis of this new method
yields an upper bound of $\tilde{O}(\sqrt{T})$ on the $\alpha$-regret and
evidences the impact of the graph structure on the rate of convergence.
Finally, we show through various experiments the validity of our approach.
- Abstract（参考訳）: グラフ上のエージェントがそれぞれの隣人と確率的バイリニアバンディットゲームをプレイするグラフ的ビリニアバンディット問題に対して,最初の後悔に基づくアプローチを提案する。
この設定は、(双)線形バンディット文学における既存の後悔に基づくアルゴリズムの使用を阻止する組み合わせNPハード問題を明らかにする。
本稿では,このギャップを埋め,不確実性に直面した楽観主義の原理を用いて,グラフィカル双線形帯域に対する最初の後悔に基づくアルゴリズムを提案する。
この新手法の理論的解析により、$\alpha$-regret に対する$\tilde{o}(\sqrt{t})$の上限が得られ、グラフ構造が収束率に与える影響が証明される。
最後に,様々な実験を通して,提案手法の有効性を示す。
関連論文リスト
- The graph alignment problem: fundamental limits and efficient algorithms [0.9246334723892301]
グラフ同型問題のノイズバージョンは、エッジの大部分を保存する2つのグラフのノード間のマッチングを見つけることを目的としている。
この論文は、この問題の基本的な情報理論的限界を理解すること、および、基礎となるデータのアライメントを回復できるアルゴリズムを設計および分析することに焦点を当てている。
論文 参考訳（メタデータ） (2024-04-18T15:31:13Z) - Stochastic Graph Bandit Learning with Side-Observations [4.910658441596583]
基礎となるグラフ構造と報酬ギャップの両方に適応するアルゴリズムを提案する。
我々の知る限りでは、この設定においてギャップ依存の上界を初めて提供するアルゴリズムである。
論文 参考訳（メタデータ） (2023-08-29T08:14:19Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - Improved Algorithms for Bandit with Graph Feedback via Regret
Decomposition [2.3034251503343466]
グラフフィードバックによるバンディットの問題は、マルチアームバンディット(MAB)問題と専門家のアドバイスによる学習の両方を一般化する。
本稿では,フィードバックグラフの分割に基づく新しいアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2022-05-30T13:07:42Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳（メタデータ） (2020-12-24T05:36:29Z) - Best Arm Identification in Graphical Bilinear Bandits [9.052414772641011]
本稿では,学習者がグラフのノードにアームを割り当てる,新しいグラフィカル双線形帯域問題を提案する。
学習者が双線形報酬の合計を最大化するグラフ割り当てを見つけたいと思う最良の腕識別問題について研究する。
論文 参考訳（メタデータ） (2020-12-14T15:25:23Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳（メタデータ） (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。