論文の概要: Online learning with noisy side observations

• arxiv url: http://arxiv.org/abs/2604.13740v1
• Date: Wed, 15 Apr 2026 11:27:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-16 20:38:32.508099
• Title: Online learning with noisy side observations
• Title（参考訳）: ノイズ側観察によるオンライン学習
• Authors: Tomáš Kocák, Gergely Neu, Michal Valko,
• Abstract要約: 本稿では,学習者自身の損失に加えて,ノイズの多いフィードバックを観察するオンライン学習問題に対して,新たな部分可観測性モデルを提案する。 この構造を重み付き有向グラフで表現し、エッジ重みは接続ノードが共有するフィードバックの品質と関係している。 我々の主な貢献は、$T$ラウンド後の$widetildeO(sqrt* T)$の後悔を保証する効率的なアルゴリズムである。
• 参考スコア（独自算出の注目度）: 23.85024184793822
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new partial-observability model for online learning problems where the learner, besides its own loss, also observes some noisy feedback about the other actions, depending on the underlying structure of the problem. We represent this structure by a weighted directed graph, where the edge weights are related to the quality of the feedback shared by the connected nodes. Our main contribution is an efficient algorithm that guarantees a regret of $\widetilde{O}(\sqrt{α^* T})$ after $T$ rounds, where $α^*$ is a novel graph property that we call the effective independence number. Our algorithm is completely parameter-free and does not require knowledge (or even estimation) of $α^*$. For the special case of binary edge weights, our setting reduces to the partial-observability models of Mannor and Shamir (2011) and Alon et al. (2013) and our algorithm recovers the near-optimal regret bounds.
• Abstract（参考訳）: 本稿では,学習者自身の損失に加えて,問題の基盤となる構造に応じて,学習者が他の行動に対する騒々しいフィードバックを観察するオンライン学習問題に対する新しい部分可観測性モデルを提案する。 この構造を重み付き有向グラフで表現し、エッジ重みは接続ノードが共有するフィードバックの品質と関係している。 我々の主な貢献は、$\widetilde{O}(\sqrt{α^* T})$の後での後悔を保証する効率的なアルゴリズムである。 我々のアルゴリズムは完全にパラメータフリーであり、$α^*$の知識(あるいは推定さえ必要としない。 二辺重みの特別な場合、我々の設定は、Mannor and Shamir (2011) と Alon et al (2013) の部分可観測モデルに還元され、我々のアルゴリズムは、ほぼ最適の後悔境界を回復する。

関連論文リスト

• Swap Regret Minimization Through Response-Based Approachability [66.39400409563976]
  オンライン最適化において,スワップ後悔という異なる概念を最小化することの問題点を考察する。 我々は、一般凸集合に対して$O(d3/2 sqrtT)$リニアスワップ後悔を保証し、集合が中央対称であるときに$O(d sqrtT)$を保証し、より単純で効率的なアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2026-02-05T23:43:25Z)
• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
  オンラインスパース線形回帰(OSLR)では,予測のために1インスタンスあたり$d$あたり$k$しかアクセスできない。 提案手法では, 過去の後悔点を大幅に改善する拡張時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-10-31T05:02:33Z)
• Rising Rested Bandits: Lower Bounds and Efficient Algorithms [15.390680055166769]
  本論文は、連続マルチアーマッドバンド(MAB)の分野である。 我々は,腕の期待される報酬が単調に非減少性であり,結束する残留包帯の特定の症例について検討した。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2024-11-06T22:00:46Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
  ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。 複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
  論文  参考訳（メタデータ） (2023-06-05T15:35:00Z)
• Learning on the Edge: Online Learning with Stochastic Feedback Graphs [12.83118601099289]
  有向フィードバックグラフが帯域幅を持つ拡張について検討する。 グラフの各ラウンドにおいて、グラフの各エッジは、それぞれのエッジに対して異なる確率で実現されるか、実現されないかのいずれかである。 我々は、独立性の重み付けされたバージョンと弱い支配数に依存する、より効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2022-10-09T11:21:08Z)
• 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)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。 そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。 後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
  論文  参考訳（メタデータ） (2022-03-19T13:39:49Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Contextual Bandits with Side-Observations [10.248045133793287]
  ソーシャルネットワークを介して接続されたユーザの推薦アルゴリズムを設計するために,両腕にサイドオブザーブメントが存在する場合のコンテキスト帯について検討する。 既存の学習アルゴリズムの素直な応用は、$Oleft(Nlog Tright)$ regretとなり、そこでは$N$がユーザ数であることを示す。
  論文  参考訳（メタデータ） (2020-06-06T19:34:50Z)

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

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