論文の概要: Oracle-Efficient Hybrid Online Learning with Unknown Distribution
- arxiv url: http://arxiv.org/abs/2401.15520v1
- Date: Sat, 27 Jan 2024 22:45:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-30 17:49:33.220563
- Title: Oracle-Efficient Hybrid Online Learning with Unknown Distribution
- Title(参考訳): 未知分散によるoracle効率のよいハイブリッドオンライン学習
- Authors: Changlong Wu, Jin Sima, Wojciech Szpankowski
- Abstract要約: 有限VCクラスに対して$tildeO(Tfrac34)$,$tildeO(Tfracp+1p+2)$に対して$alpha$fat-shattering dimensionを持つクラスに対して$tildeO(Tfracp+1p+2)$という,計算効率のよいオンライン予測器が存在することを示す。
すると、結果が$K$変更で分布をシフトするシナリオにまで拡張され、$tildeO(Tfrac45Kfrac15)が返り咲く。
- 参考スコア(独自算出の注目度): 16.73555330791045
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of oracle-efficient hybrid online learning when the
features are generated by an unknown i.i.d. process and the labels are
generated adversarially. Assuming access to an (offline) ERM oracle, we show
that there exists a computationally efficient online predictor that achieves a
regret upper bounded by $\tilde{O}(T^{\frac{3}{4}})$ for a finite-VC class, and
upper bounded by $\tilde{O}(T^{\frac{p+1}{p+2}})$ for a class with $\alpha$
fat-shattering dimension $\alpha^{-p}$. This provides the first known
oracle-efficient sublinear regret bounds for hybrid online learning with an
unknown feature generation process. In particular, it confirms a conjecture of
Lazaric and Munos (JCSS 2012). We then extend our result to the scenario of
shifting distributions with $K$ changes, yielding a regret of order
$\tilde{O}(T^{\frac{4}{5}}K^{\frac{1}{5}})$. Finally, we establish a regret of
$\tilde{O}((K^{\frac{2}{3}}(\log|\mathcal{H}|)^{\frac{1}{3}}+K)\cdot
T^{\frac{4}{5}})$ for the contextual $K$-armed bandits with a finite policy set
$\mathcal{H}$, i.i.d. generated contexts from an unknown distribution, and
adversarially generated costs.
- Abstract(参考訳): 未知のi.d.プロセスによって特徴が生成され、ラベルが逆向きに生成される場合、オラクル効率の良いハイブリッドオンライン学習の問題を考察する。
ERMオラクルへのアクセスを仮定すると、有限VCクラスに対して$\tilde{O}(T^{\frac{3}{4}})$、および$\tilde{O}(T^{\frac{p+1}{p+2}})$に対して$\alpha$fat-shattering dimension$\alpha^{-p}$で満たされた後悔の上界を達成する計算効率の良いオンライン予測器が存在することを示す。
これは、未知の機能生成プロセスを持つハイブリッドオンライン学習に、最初のoracle- efficient sublinear regret boundsを提供する。
特に、Lazaric and Munos(JCSS 2012)の予想を確認している。
そして、その結果を$k$の変更でディストリビューションをシフトするというシナリオに拡張し、$\tilde{o}(t^{\frac{4}{5}}k^{\frac{1}{5}})$という順序の後悔を与えます。
最後に、ある未知の分布から生成されたコンテキストと反対に生成されたコストから生じる有限のポリシーセット$K$武装の包帯に対して、$\tilde{O}((K^{\frac{2}{3}}(\log|\mathcal{H}|)^{\frac{1}{3}}+K)\cdot T^{\frac{4}{5}})$の後悔を確立する。
関連論文リスト
- Online Learning of Halfspaces with Massart Noise [47.71073318490341]
我々はMassartノイズの存在下でのオンライン学習の課題について検討する。
計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。
我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
論文 参考訳(メタデータ) (2024-05-21T17:31:10Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳(メタデータ) (2022-10-15T09:22:22Z) - Optimism in Face of a Context: Regret Guarantees for Stochastic
Contextual MDP [46.86114958340962]
我々は,最小到達可能性仮定の下での文脈的MDPに対する後悔のアルゴリズムを提案する。
我々のアプローチは、一般関数近似を用いた文脈的MDPに適用された最初の楽観的アプローチである。
論文 参考訳(メタデータ) (2022-07-22T15:00:15Z) - Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries [29.598518028635716]
オンライン学習の最悪のケース分析を超越した,オラクル効率のアルゴリズムについて検討する。
このスムーズな分析設定のために,本研究は,スムーズな相手を持つオンライン学習のための最初のオラクル効率のアルゴリズムを提供する。
論文 参考訳(メタデータ) (2022-02-17T09:49:40Z) - Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
線形関数近似を用いた強化学習における最短経路 (SSP) 問題について検討し, 遷移カーネルを未知モデルの線形混合として表現する。
本稿では,線形混合SSPを学習するための新しいアルゴリズムを提案し,このアルゴリズムにより,$tilde O(d B_star1.5sqrtK/c_min)$ regretを実現する。
論文 参考訳(メタデータ) (2021-10-25T08:34:00Z) - Model Selection with Near Optimal Rates for Reinforcement Learning with
General Model Classes [27.361399036211694]
有限地平線エピソディック強化学習(RL)問題に対するモデル選択の問題に対処する。
モデル選択フレームワークでは、$mathcalP*$の代わりに、遷移カーネルのネストされたファミリーが$M$を与えられる。
textttARL-GENが$TildemathcalO(d_mathcalE* H2+sqrtd_mathcalE* mathbbM* H2T)$の後悔を得ることを示す。
論文 参考訳(メタデータ) (2021-07-13T05:00:38Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳(メタデータ) (2021-03-25T18:52:17Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳(メタデータ) (2021-01-29T18:57:52Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳(メタデータ) (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。