論文の概要: Online learning with Erdős-Rényi side-observation graphs

• arxiv url: http://arxiv.org/abs/2604.25271v1
• Date: Tue, 28 Apr 2026 06:29:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-29 16:49:17.734651
• Title: Online learning with Erdős-Rényi side-observation graphs
• Title（参考訳）: Erdés-Rényi側観測グラフを用いたオンライン学習
• Authors: Tomáš Kocák, Gergely Neu, Michal Valko,
• Abstract要約: 本研究では,学習者が実際に選択した腕の横にある多数の腕の損失を観察できるような,逆方向のマルチアームバンディット問題について考察する。 本研究は,すべての非調波アームが,互いに独立に,かつ学習者の行動によって,固定的だが未知の確率$r$で損失を露呈する事例について検討する。 我々は、$N$アームのバンディット問題で$T$ラウンドを行った後、最初のアルゴリズムの期待された後悔は$O(sqrt(T /r) log N )$ whenever $rge(log T)/(2であることを示した。
• 参考スコア（独自算出の注目度）: 23.85024184793822
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider adversarial multi-armed bandit problems where the learner is allowed to observe losses of a number of arms beside the arm that it actually chose. We study the case where all non-chosen arms reveal their loss with a fixed but unknown probability $r$, independently of each other and the action of the learner. We propose two algorithms that work for different ranges of $r$. We show that after $T$ rounds in a bandit problem with $N$ arms, the expected regret of our first algorithm is $O(\sqrt{(T /r) \log N })$ whenever $r\ge(\log T)/(2N)$, while our second algorithm achieves a regret of $O(\sqrt{(T/r) \log (N+T)})$ for smaller values of $r$. We also give a quick estimation procedure that decides the range of~$r$. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know~$r$.
• Abstract（参考訳）: 本研究では,学習者が実際に選択した腕の横にある多数の腕の損失を観察できるような,逆方向のマルチアームバンディット問題について考察する。 本研究は,すべての非調波アームが,互いに独立に,かつ学習者の行動によって,固定的だが未知の確率$r$で損失を露呈する事例について検討する。 異なる範囲の$r$に対して動作する2つのアルゴリズムを提案する。 我々は、$N$の腕を持つバンディット問題における$T$のラウンドの後、最初のアルゴリズムの期待された後悔は$O(\sqrt{(T /r) \log N })$/$r\ge(\log T)/(2N)$であり、2番目のアルゴリズムは$O(\sqrt{(T/r) \log (N+T)}$の後悔を達成する。 また、-$r$の範囲を決定するクイック推定手順も提供します。 すべての境界は、任意のアルゴリズムの最も達成可能な性能の対数的要素の範囲内であり、その値は~$r$である。

関連論文リスト

• On Interpolating Experts and Multi-Armed Bandits [1.9497955504539408]
  我々は、$mathbfm$-MABに対して厳密なミニマックス後悔境界を証明し、その純粋な探索バージョンである$mathbfm$-BAIに対して最適なPACアルゴリズムを設計する。 その結果、フィードバックグラフのいくつかのファミリに対して、厳密なミニマックス後悔境界を得た。
  論文  参考訳（メタデータ） (2023-07-14T10:38:30Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem [13.69077222007053]
  従来のマルチアームバンディット問題(英語版)のバリエーションである$K$のデュエルリングバンディット問題(英語版)について検討し、フィードバックをペア比較の形で得られる。 我々は、$O(K2log(K)) + O(Klog(T))$ in $O(log(T))$ rounds を後悔する。 実世界の様々なデータセットに対する計算実験において、$O(log(T))$ラウンドを用いたアルゴリズムが完全に同じ性能を達成することが観察された。
  論文  参考訳（メタデータ） (2022-09-25T00:23:55Z)
• Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms [30.024167992890916]
  そこで本研究では,学習者が200ドル(約1万2000円)の帯域幅のタスクに直面する決定について検討する。 敵は各タスクの最適なアームを、M$アームのより小さな(しかし未知の)サブセットで選択することを制約される。 境界は既知のもの(非定常的メタラーニング設定)、あるいは未知のもの(非定常的バンディット設定)である。
  論文  参考訳（メタデータ） (2022-02-25T22:28:01Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)

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

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