論文の概要: Communication-Constrained Bandits under Additive Gaussian Noise

• arxiv url: http://arxiv.org/abs/2304.12680v2
• Date: Tue, 6 Jun 2023 10:22:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-07 20:08:11.034976
• Title: Communication-Constrained Bandits under Additive Gaussian Noise
• Title（参考訳）: 付加ガウス雑音下における通信制約帯域
• Authors: Prathamesh Mayekar, Jonathan Scarlett, and Vincent Y.F. Tan
• Abstract要約: クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
• 参考スコア（独自算出の注目度）: 111.06688156723018
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a distributed stochastic multi-armed bandit where a client supplies the learner with communication-constrained feedback based on the rewards for the corresponding arm pulls. In our setup, the client must encode the rewards such that the second moment of the encoded rewards is no more than $P$, and this encoded reward is further corrupted by additive Gaussian noise of variance $\sigma^2$; the learner only has access to this corrupted reward. For this setting, we derive an information-theoretic lower bound of $\Omega\left(\sqrt{\frac{KT}{\mathtt{SNR} \wedge1}} \right)$ on the minimax regret of any scheme, where $ \mathtt{SNR} := \frac{P}{\sigma^2}$, and $K$ and $T$ are the number of arms and time horizon, respectively. Furthermore, we propose a multi-phase bandit algorithm, $\mathtt{UE\text{-}UCB++}$, which matches this lower bound to a minor additive factor. $\mathtt{UE\text{-}UCB++}$ performs uniform exploration in its initial phases and then utilizes the {\em upper confidence bound }(UCB) bandit algorithm in its final phase. An interesting feature of $\mathtt{UE\text{-}UCB++}$ is that the coarser estimates of the mean rewards formed during a uniform exploration phase help to refine the encoding protocol in the next phase, leading to more accurate mean estimates of the rewards in the subsequent phase. This positive reinforcement cycle is critical to reducing the number of uniform exploration rounds and closely matching our lower bound.
• Abstract（参考訳）: そこで本研究では,クライアントが学習者に,対応するアームプルに対する報奨に基づいてコミュニケーション制約付きフィードバックを提供する分散確率的多腕バンディットについて検討する。 私たちの設定では、クライアントは、エンコードされた報酬の第二のモーメントが$p$以下であるように、報酬をエンコードする必要があります。 この設定のために、情報理論的な下限 $\omega\left(\sqrt{\frac{kt}{\mathtt{snr} \wedge1}} \right)$ が任意のスキームのミニマックス後悔に基づいて導出され、ここで $ \mathtt{snr} := \frac{p}{\sigma^2}$, $k$ と $t$ はそれぞれ腕数と時間軸数である。 さらに、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$\mathtt{UE\text{-}UCB++}$を提案する。 $\mathtt{UE\text{-}UCB++}$は初期フェーズで一様探索を行い、最終フェーズで {\em upper confidence bound }(UCB)banditアルゴリズムを利用する。 $\mathtt{UE\text{-}UCB++}$の興味深い特徴は、一様探索フェーズで生成された平均報酬の粗い推定が、次のフェーズで符号化プロトコルを洗練させ、その後のフェーズにおける報酬のより正確な平均見積もりをもたらすことである。 この正の補強サイクルは、均一な探査ラウンドの数を減らし、我々の下界と密接に一致する。

関連論文リスト

• Stochastic Bandits Robust to Adversarial Attacks [33.278131584647745]
  本稿では,敵攻撃に対して頑健なマルチアームバンディットアルゴリズムについて検討する。 我々は、攻撃予算の知識の有無に関わらず、このモデルの2つのケースを調査する。 我々は、加法的あるいは乗法的な$C$依存項を持つ後悔境界を持つ2種類のアルゴリズムを考案する。
  論文  参考訳（メタデータ） (2024-08-16T17:41:35Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Nearly Minimax Optimal Regret for Multinomial Logistic Bandit [8.087699764574788]
  本研究では,学習エージェントが文脈情報に基づいて順にアソシエーションを選択する,文脈多項ロジット(MNL)バンディット問題について検討する。 特に最大品位が$K$の場合には、下限と上限の差が顕著である。 定数時間アルゴリズム OFU-MNL+ を提案し, 一致する上限を $tildeO(dsqrtsmash[b]T/K)$ とする。
  論文  参考訳（メタデータ） (2024-05-16T06:07:31Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。 ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。 我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
  論文  参考訳（メタデータ） (2023-02-07T02:22:31Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm [14.214707836697823]
  破損したバンドイット問題、すなわち、$k$未知の報酬分布を持つ多重武装バンドイット問題について検討する。 本稿では,ハマー推定器上に構築した,破損した盗賊に対する新しいUPB型アルゴリズムを提案する。 異なる報酬分布と異なるレベルの汚職に対する腐敗した包帯の解法におけるHubUCBとSeqHubUCBの有効性を実験的に説明した。
  論文  参考訳（メタデータ） (2022-03-07T07:44:05Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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