論文の概要: Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds

• arxiv url: http://arxiv.org/abs/2003.03490v2
• Date: Mon, 26 Apr 2021 09:17:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-25 19:13:49.323462
• Title: Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds
• Title（参考訳）: アクションセットの変更による逆オンライン学習:近似レグレット境界を用いた効率的なアルゴリズム
• Authors: Ehsan Emamjomeh-Zadeh, Chen-Yu Wei, Haipeng Luo, David Kempe
• Abstract要約: 睡眠の専門家やバンドイットによるオンライン学習の問題を再考する。 各タイムステップにおいて、アルゴリズムが選択できるアクションのサブセットのみが利用可能である。 我々は、一般的な睡眠専門家/バンド問題に対して、アポキシマ-レグレット保証を提供するアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 48.312484940846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the problem of online learning with sleeping experts/bandits: in each time step, only a subset of the actions are available for the algorithm to choose from (and learn about). The work of Kleinberg et al. (2010) showed that there exist no-regret algorithms which perform no worse than the best ranking of actions asymptotically. Unfortunately, achieving this regret bound appears computationally hard: Kanade and Steinke (2014) showed that achieving this no-regret performance is at least as hard as PAC-learning DNFs, a notoriously difficult problem. In the present work, we relax the original problem and study computationally efficient no-approximate-regret algorithms: such algorithms may exceed the optimal cost by a multiplicative constant in addition to the additive regret. We give an algorithm that provides a no-approximate-regret guarantee for the general sleeping expert/bandit problems. For several canonical special cases of the problem, we give algorithms with significantly better approximation ratios; these algorithms also illustrate different techniques for achieving no-approximate-regret guarantees.
• Abstract（参考訳）: 睡眠の専門家/バンドによるオンライン学習の問題を再検討する: 各ステップでは、アルゴリズムが選択する(そして学ぶ)ためのアクションのサブセットのみが利用可能です。 kleinberg et al. (2010) の研究は、漸近的に最良な行動ランク付けを行うようなアルゴリズムは存在しないことを示した。 Kanade と Steinke (2014) は、この非回帰性能を達成することは、少なくともPAC学習型 DNF と同じくらい難しいことを示しており、これは非常に難しい問題である。 本研究では,本課題を緩和し,計算効率のよい非近似回帰アルゴリズムについて検討する。 我々は,一般の睡眠専門家/バンドイット問題に対して,無防備な保証を提供するアルゴリズムを提案する。 この問題のいくつかの標準的特殊ケースに対して、近似比が大幅に向上したアルゴリズムを与え、これらのアルゴリズムはまた、非近似-回帰保証を達成するための異なるテクニックも示している。

関連論文リスト

• Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning [4.10375234787249]
  教師なし学習問題に対する効率的なアルゴリズム設計のための枠組みを提案する。 我々のフレームワークは,雑音の存在下で演算回路を学習するメタアルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2023-11-13T12:26:25Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Dual Algorithmic Reasoning [9.701208207491879]
  本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。 アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。 次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
  論文  参考訳（メタデータ） (2023-02-09T08:46:23Z)
• Causal Bandits without Graph Learning [28.021500949026766]
  我々は,原子間干渉を用いた報酬ノードの親ノード探索のための効率的なアルゴリズムを開発した。 報奨ノードが複数の親を持つ場合にアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2023-01-26T20:27:14Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)
• TopRank+: A Refinement of TopRank Algorithm [0.0]
  トポロジカルソートに基づく新しいオンライン学習アルゴリズムが提案された。 本研究では、ある暗黙関数の混合と拡張の手法を用いて、不等式に対してより厳密で反復的なログのような境界を与える。
  論文  参考訳（メタデータ） (2020-01-21T15:44:44Z)

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

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