論文の概要: Bounds on the price of feedback for mistake-bounded online learning
- arxiv url: http://arxiv.org/abs/2401.05794v2
- Date: Wed, 17 Jan 2024 07:32:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 19:28:43.378676
- Title: Bounds on the price of feedback for mistake-bounded online learning
- Title（参考訳）: ミスバウンドオンライン学習におけるフィードバックの価格に関する考察
- Authors: Jesse Geneson and Linus Tang
- Abstract要約: 各種オンライン学習シナリオ(Auer and Long, Machine Learning, 1999)の最悪のケース境界を改善した。
本研究では,2因子による遅延曖昧性強化学習のための上界,2.41因子による関数群構成学習のための上界を抽出した。
また、同じ論文から$k$の関数族の構成を$Theta(lnk)$の係数で学習するための下界も改善し、上界を定数係数に整合させる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We improve several worst-case bounds for various online learning scenarios
from (Auer and Long, Machine Learning, 1999). In particular, we sharpen an
upper bound for delayed ambiguous reinforcement learning by a factor of 2 and
an upper bound for learning compositions of families of functions by a factor
of 2.41. We also improve a lower bound from the same paper for learning
compositions of $k$ families of functions by a factor of $\Theta(\ln{k})$,
matching the upper bound up to a constant factor. In addition, we solve a
problem from (Long, Theoretical Computer Science, 2020) on the price of bandit
feedback with respect to standard feedback for multiclass learning, and we
improve an upper bound from (Feng et al., Theoretical Computer Science, 2023)
on the price of $r$-input delayed ambiguous reinforcement learning by a factor
of $r$, matching a lower bound from the same paper up to the leading term.
- Abstract（参考訳）: 各種オンライン学習シナリオ(Auer and Long, Machine Learning, 1999)の最悪のケース境界を改善した。
特に,2因子による遅延曖昧な強化学習のための上界と2.41因子による関数の族組成の学習のための上界を抽出した。
また、関数の族$k$の合成を$\Theta(\ln{k})$の係数で学習するために同じ論文から下界を改良し、上界を定数因子に合わせる。
さらに,マルチクラス学習における標準的なフィードバックに対するバンディットフィードバックの価格(長期,理論計算機科学,2020)の問題点を解決し,(feng et al., theoretical computer science, 2023) の上限を,r$-input delay ambiguous reinforcement learning の価格を,同じ論文から先行項までの下限と一致する$r$ で改善する。
関連論文リスト
- On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective [8.104151304193216]
我々は、差分的プライベート(DP)オンライン学習アルゴリズムに対して、より低いバウンダリを提供する。
我々の研究は、DP-オンライン学習の下位境界の設定に向けた最初の成果である。
論文 参考訳（メタデータ） (2024-02-26T17:49:37Z) - Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss [25.50155563108198]
フルインフォメーションフィードバックを用いたオンライン構造化予測について検討する。
我々はエクスプロイト・ザ・サロゲート・ギャップ・フレームワークをemphFenchelによるオンライン構造化予測に拡張する。
論文 参考訳（メタデータ） (2024-02-13T02:36:41Z) - Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。
本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
論文 参考訳（メタデータ） (2023-10-02T19:59:39Z) - Generalization Analysis for Contrastive Representation Learning [80.89690821916653]
既存の一般化誤差境界は負の例の数$k$に線形に依存する。
対数項まで$k$に依存しないコントラスト学習のための新しい一般化境界を確立する。
論文 参考訳（メタデータ） (2023-02-24T01:03:56Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T17:26:39Z) - Fine-Grained Distribution-Dependent Learning Curves [27.09513298165498]
学習曲線はラベル付き入力サンプル数の関数として学習アルゴリズムの予測誤差をプロットする。
本稿では,Bousquet et alの最近の成果を改良し,改良する,粒状PACと呼ばれる新しい次元特性について紹介する。
我々の特徴は、きめ細かい境界を提供することによって学習曲線の構造に新たな光を当てることである。
論文 参考訳（メタデータ） (2022-08-31T03:29:21Z) - Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
我々は、効率よく非結合な学習力学を確立し、各プレイヤーのトリガー後悔は、プレイの繰り返しの後に$O(log T)$として成長する。
これにより、これまでよく知られていた$O(T1/4)$よりも指数関数的に改善される。
論文 参考訳（メタデータ） (2022-08-20T20:48:58Z) - There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning
for Mazes [64.05903267230467]
相互理解性は,強化学習システムにおける信頼性に不可欠なビルディングブロックである。
場合によっては、最適性を保ちつつ、政策の解釈可能性を達成することができることを示す。
論文 参考訳（メタデータ） (2022-06-09T04:23:26Z) - Rebalanced Siamese Contrastive Mining for Long-Tailed Recognition [120.80038161330623]
教師付きコントラスト学習は、元のバッチレベルとシームズバッチレベルの両方において、二重クラス不均衡の問題に悩まされていることを示す。
コントラスト計算のための情報的ペアを抽出し,表現学習を改善するために,教師付き強正・負のペアマイニングを提案する。
論文 参考訳（メタデータ） (2022-03-22T07:30:38Z) - Near-Optimal No-Regret Learning for Correlated Equilibria in
Multi-Player General-Sum Games [104.74734408204749]
マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。
外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
論文 参考訳（メタデータ） (2021-11-11T01:19:53Z) - Batch Value-function Approximation with Only Realizability [17.692408242465763]
バッチ強化学習(RL):探索データセットからQstar$を学習する。
我々のアルゴリズムであるBVFTは、トーナメントの手順を通じて硬さ予想(探索データというより強い概念の下では)を破る。
また、BVFTが他の拡張と開問題の間のモデル選択にどのように適用できるかについても論じる。
論文 参考訳（メタデータ） (2020-08-11T20:09:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。