論文の概要: History-Restricted Online Learning
- arxiv url: http://arxiv.org/abs/2205.14519v1
- Date: Sat, 28 May 2022 20:52:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-31 15:24:37.703883
- Title: History-Restricted Online Learning
- Title(参考訳): 履歴制限付きオンライン学習
- Authors: Jon Schneider and Kiran Vodrahalli
- Abstract要約: 本稿では,履歴制限のないオンライン学習アルゴリズムについて紹介する。
オンライン学習アルゴリズム $mathcalA$ が$M$-history-restricted であるとは、その時点での出力 $t$ が$M$以前の報酬の関数として書けることである。
- 参考スコア(独自算出の注目度): 15.564663451885371
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We introduce the concept of history-restricted no-regret online learning
algorithms. An online learning algorithm $\mathcal{A}$ is
$M$-history-restricted if its output at time $t$ can be written as a function
of the $M$ previous rewards. This class of online learning algorithms is quite
natural to consider from many perspectives: they may be better models of human
agents and they do not store long-term information (thereby ensuring ``the
right to be forgotten''). We first demonstrate that a natural approach to
constructing history-restricted algorithms from mean-based no-regret learning
algorithms (e.g. running Hedge over the last $M$ rounds) fails, and that such
algorithms incur linear regret. We then construct a history-restricted
algorithm that achieves a per-round regret of $\Theta(1/\sqrt{M})$, which we
complement with a tight lower bound. Finally, we empirically explore
distributions where history-restricted online learners have favorable
performance compared to other no-regret algorithms.
- Abstract(参考訳): 本稿では,歴史に制約のないオンライン学習アルゴリズムの概念を紹介する。
オンライン学習アルゴリズム $\mathcal{A}$ が$M$-history-restricted であるとは、その時の出力 $t$ が$M$以前の報酬の関数として書けることをいう。
このタイプのオンライン学習アルゴリズムは、多くの観点から考えると、非常に自然である: それらは人間のエージェントのより良いモデルであり、長期的な情報を保存しないかもしれない。
まず,平均ベース非レグレット学習アルゴリズム(例えば,過去$m$ラウンドにわたってヘッジを実行する)から履歴制限付きアルゴリズムを構築するための自然なアプローチが失敗し,そのようなアルゴリズムが線形後悔を引き起こすことを実証する。
そして、履歴制限付きアルゴリズムを構築し、1回あたりの後悔が$\theta(1/\sqrt{m})$となるようにします。
最後に、履歴制限のあるオンライン学習者が他の非学習アルゴリズムと比較して好適な性能を持つ分布を実証的に探求する。
関連論文リスト
- Decoupling Learning and Decision-Making: Breaking the
$\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with
First-Order Methods [8.065772738358797]
意思決定から学習を分離する新しいアルゴリズムフレームワークを導入する。
我々は、この新しいフレームワークで、一階のメソッドが、後悔する$mathcalO(sqrtT)$を達成できることを示します。
論文 参考訳(メタデータ) (2024-02-11T05:35:50Z) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳(メタデータ) (2023-10-28T13:01:10Z) - Simple online learning with consistent oracle [55.43220407902113]
オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
論文 参考訳(メタデータ) (2023-08-15T21:50:40Z) - 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) - Emphatic Algorithms for Deep Reinforcement Learning [43.17171330951343]
時間差学習アルゴリズムは関数近似とオフポリシーサンプリングを組み合わせると不安定になる。
強調時間差(ETD($lambda$)アルゴリズム)は、TD($lambda$)更新を適切に重み付けすることで線形の場合の収束を保証する。
本稿では,ETD($lambda$)をフォワードビュー・マルチステップ・リターンを用いた一般的な深層強化学習アルゴリズムに適用することにより,性能が低下することを示す。
論文 参考訳(メタデータ) (2021-06-21T12:11:39Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳(メタデータ) (2021-01-08T18:55:07Z) - Online Linear Optimization with Many Hints [72.4277628722419]
本研究では,学習者が決定に先立って各ラウンドでK$"hint"ベクトルにアクセス可能なオンライン線形最適化(OLO)問題について検討する。
この設定では、コストベクトルと正の相関を持つ$K$ヒントの凸結合が存在する場合、対数後悔を求めるアルゴリズムを考案する。
論文 参考訳(メタデータ) (2020-10-06T23:25:05Z) - Adversarial Online Learning with Changing Action Sets: Efficient
Algorithms with Approximate Regret Bounds [48.312484940846]
睡眠の専門家やバンドイットによるオンライン学習の問題を再考する。
各タイムステップにおいて、アルゴリズムが選択できるアクションのサブセットのみが利用可能である。
我々は、一般的な睡眠専門家/バンド問題に対して、アポキシマ-レグレット保証を提供するアルゴリズムを提供する。
論文 参考訳(メタデータ) (2020-03-07T02:13:21Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳(メタデータ) (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。