論文の概要: Online combinatorial optimization with stochastic decision sets and adversarial losses

• arxiv url: http://arxiv.org/abs/2604.25269v1
• Date: Tue, 28 Apr 2026 06:28:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-29 16:49:17.73372
• Title: Online combinatorial optimization with stochastic decision sets and adversarial losses
• Title（参考訳）: 確率的決定集合と逆損失を伴うオンライン組合せ最適化
• Authors: Gergely Neu, Michal Valko,
• Abstract要約: 本研究では、信頼できない複合動作の可用性に対処できる学習アルゴリズムについて研究する。 我々のアルゴリズムは、Counting Asleep Timesと呼ばれる新しい損失推定手法に依存している。 その結果,睡眠バンドイット問題に対する効率的なアルゴリズムにより,最もよく知られた性能保証の大幅な改善が得られた。
• 参考スコア（独自算出の注目度）: 26.805281688186657
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most work on sequential learning assumes a fixed set of actions that are available all the time. However, in practice, actions can consist of picking subsets of readings from sensors that may break from time to time, road segments that can be blocked or goods that are out of stock. In this paper we study learning algorithms that are able to deal with stochastic availability of such unreliable composite actions. We propose and analyze algorithms based on the Follow-The-Perturbed-Leader prediction method for several learning settings differing in the feedback provided to the learner. Our algorithms rely on a novel loss estimation technique that we call Counting Asleep Times. We deliver regret bounds for our algorithms for the previously studied full information and (semi-)bandit settings, as well as a natural middle point between the two that we call the restricted information setting. A special consequence of our results is a significant improvement of the best known performance guarantees achieved by an efficient algorithm for the sleeping bandit problem with stochastic availability. Finally, we evaluate our algorithms empirically and show their improvement over the known approaches.
• Abstract（参考訳）: シーケンシャルラーニングに関するほとんどの作業は、常に利用可能な一定のアクションセットを前提としています。 しかし、実際には、アクションは、時々壊れるセンサー、ブロックされる道路セグメント、在庫切れの商品から、読み物のサブセットを拾うことで構成できる。 本稿では,そのような信頼できない複合動作の確率的利用性に対処できる学習アルゴリズムについて検討する。 本稿では,学習者に提供されるフィードバックによって異なる学習環境に対して,Follow-The-Perturbed-Leader予測法に基づくアルゴリズムを提案し,解析する。 我々のアルゴリズムは、Counting Asleep Timesと呼ばれる新しい損失推定手法に依存している。 我々は、以前に研究された全情報と(半)帯域設定のためのアルゴリズムに対する後悔の限界と、制限された情報設定と呼ばれる2つの間の自然な中間点を提供する。 以上の結果から,寝たきり問題と確率的可用性の問題に対する効率的なアルゴリズムにより,最もよく知られた性能保証の大幅な改善が得られた。 最後に、我々のアルゴリズムを実証的に評価し、既知のアプローチよりも改善したことを示す。

関連論文リスト

• Efficient learning by implicit exploration in bandit problems with side observations [21.943714947100414]
  本研究では,学習者に伝達される情報が,全情報と盗聴フィードバックの間にある状況を把握する部分的可観測性モデルに基づくオンライン学習問題を考察する。 本稿では,観測システムを知ることなく,ほぼ最適の後悔の保証を享受するアルゴリズムを提案する。 また,学習者のフィードバックが半帯域と完全フィードバックの間にあるオンライン最適化問題をモデル化する部分的情報設定も定義する。
  論文  参考訳（メタデータ） (2026-04-27T14:45:39Z)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
  論文  参考訳（メタデータ） (2025-10-20T02:28:08Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Metalearning Linear Bandits by Prior Update [7.519872646378836]
  完全なベイズ的アプローチは、問題のパラメータは既知の事前から生成されると仮定するが、実際にはそのような情報は欠落することが多い。 この問題は、ある部分的な情報を持つ意思決定設定において悪化し、不特定事前の使用は、探索の質が悪く、性能が劣る可能性がある。 この研究において、線形帯域幅とガウス事前の文脈において、事前推定が真の事前に十分近い限り、不特定事前を用いたアルゴリズムの性能は真の先行を用いたアルゴリズムのそれに近いことを証明した。
  論文  参考訳（メタデータ） (2021-07-12T11:17:01Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
  オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。 我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-01T17:59:19Z)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。 我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
  論文  参考訳（メタデータ） (2020-05-18T08:41:39Z)
• Delay-Adaptive Learning in Generalized Linear Contextual Bandits [18.68458152442088]
  遅延設定に適応した2つのよく知られたアルゴリズムの性能について検討する。 本稿では,この2つのアルゴリズムを遅延処理に適応させる方法について述べる。 この結果は,文脈的盗賊文学の広範な景観に寄与する。
  論文  参考訳（メタデータ） (2020-03-11T09:12:44Z)
• Learning with Differentiable Perturbed Optimizers [54.351317101356614]
  本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。 提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。 本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
  論文  参考訳（メタデータ） (2020-02-20T11:11:32Z)

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

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