論文の概要: Adversarial Online Learning with Temporal Feedback Graphs
- arxiv url: http://arxiv.org/abs/2407.00571v1
- Date: Sun, 30 Jun 2024 03:14:17 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-04 02:36:46.467167
- Title: Adversarial Online Learning with Temporal Feedback Graphs
- Title(参考訳): 時間フィードバックグラフを用いた対人オンライン学習
- Authors: Khashayar Gatmiry, Jon Schneider,
- Abstract要約: 本稿では,ラウンド$t$での学習者の行動が,ラウンドの特定のサブセットの損失にのみ依存できるような,専門家のアドバイスによる予測のバリエーションについて検討する。
本稿では,このグラフのサブ閥間で損失を分配する戦略に基づいて,この設定のための新しい学習アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 13.267203883254087
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a variant of prediction with expert advice where the learner's action at round $t$ is only allowed to depend on losses on a specific subset of the rounds (where the structure of which rounds' losses are visible at time $t$ is provided by a directed "feedback graph" known to the learner). We present a novel learning algorithm for this setting based on a strategy of partitioning the losses across sub-cliques of this graph. We complement this with a lower bound that is tight in many practical settings, and which we conjecture to be within a constant factor of optimal. For the important class of transitive feedback graphs, we prove that this algorithm is efficiently implementable and obtains the optimal regret bound (up to a universal constant).
- Abstract(参考訳): 本稿では,ラウンド$t$における学習者の行動がラウンドの特定のサブセットの損失にのみ依存できるような,専門家のアドバイスによる予測のバリエーションについて検討する。
本稿では,このグラフのサブ閥間で損失を分配する戦略に基づいて,この設定のための新しい学習アルゴリズムを提案する。
我々はこれを、多くの実践的な設定において厳密な下限で補完し、最適の定数要素内にあると推測する。
推移的フィードバックグラフの重要なクラスについて、このアルゴリズムは効率的に実装可能であり、最適後悔境界(普遍定数まで)が得られることを証明する。
関連論文リスト
- LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
敵は、学習者に未知の任意の数kの損失関数を破損させることで、外れ値を導入することができる。
我々は,任意の数kで損失関数を破損させることで,敵が外乱を発生させることができる,頑健なオンラインラウンド最適化フレームワークを提案する。
論文 参考訳(メタデータ) (2024-08-12T17:08:31Z) - Efficient Contextual Bandits with Uninformed Feedback Graphs [48.77120088347271]
フィードバックグラフを持つバンディットは、完全な情報と古典的なバンディットの問題を補間する強力なオンライン学習モデルである。
ここでは,2乗損失ではなくログ損失を用いてグラフを学習し,良好な後悔の保証を得ることが重要であることを示す。
論文 参考訳(メタデータ) (2024-02-12T23:50:47Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T17:26:39Z) - 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) - No-Regret Learning with Unbounded Losses: The Case of Logarithmic
Pooling [12.933990572597583]
対数プール法(対数プール)として知られる基本的および実用的アグリゲーション法に焦点をあてる。
オンラインの対戦環境において,最適なパラメータ集合を学習する問題を考察する。
本稿では,O(sqrtT log T)$experied regretに達する方法で,専門家の重みを学習するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-22T22:27:25Z) - 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) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳(メタデータ) (2020-12-10T15:40:07Z) - Online non-convex optimization with imperfect feedback [33.80530308979131]
非損失を伴うオンライン学習の問題を考える。
フィードバックの観点からは、学習者が各段階における損失関数の不正確なモデル(または構成)を観測すると仮定する。
本稿では,二元平均化に基づく混合戦略学習政策を提案する。
論文 参考訳(メタデータ) (2020-10-16T16:53:13Z) - Reinforcement Learning with Feedback Graphs [69.1524391595912]
エージェントがステップ毎に追加のフィードバックを受けた場合,決定過程におけるエピソード強化学習について検討する。
状態-作用対上のフィードバックグラフを用いてこの設定を定式化し、モデルベースのアルゴリズムが追加のフィードバックを利用してよりサンプル効率のよい学習を行うことを示す。
論文 参考訳(メタデータ) (2020-05-07T22:35:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。