論文の概要: Nonstochastic Bandits and Experts with Arm-Dependent Delays

• arxiv url: http://arxiv.org/abs/2111.01589v1
• Date: Tue, 2 Nov 2021 13:36:11 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-03 18:04:34.058903
• Title: Nonstochastic Bandits and Experts with Arm-Dependent Delays
• Title（参考訳）: 腕依存遅延の非定型バンディットと専門家
• Authors: Dirk van der Hoeven and Nicol\`o Cesa-Bianchi
• Abstract要約: 遅延が時間と腕に依存するような遅延環境で,非確率的な盗賊や専門家について検討する。 私たちの分析では、ドリフトに縛られた小説にヒンジを付け、1ラウンドのルックアヘッドを与えられた場合、アルゴリズムがどれだけの精度で実行できるかを測定しました。
• 参考スコア（独自算出の注目度）: 17.272515865592542
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study nonstochastic bandits and experts in a delayed setting where delays depend on both time and arms. While the setting in which delays only depend on time has been extensively studied, the arm-dependent delay setting better captures real-world applications at the cost of introducing new technical challenges. In the full information (experts) setting, we design an algorithm with a first-order regret bound that reveals an interesting trade-off between delays and losses. We prove a similar first-order regret bound also for the bandit setting, when the learner is allowed to observe how many losses are missing. These are the first bounds in the delayed setting that depend on the losses and delays of the best arm only. When in the bandit setting no information other than the losses is observed, we still manage to prove a regret bound through a modification to the algorithm of Zimmert and Seldin (2020). Our analyses hinge on a novel bound on the drift, measuring how much better an algorithm can perform when given a look-ahead of one round.
• Abstract（参考訳）: 遅延が時間と腕の両方に依存するような遅延設定で非定型的な盗賊や専門家を調査した。 遅延が時間にのみ依存する設定は、広く研究されているが、アーム依存の遅延設定は、新しい技術的課題を導入するコストで、現実世界のアプリケーションをよりよくキャプチャする。 完全な情報(エキスパート)設定では、遅延と損失の間の興味深いトレードオフを示す一階の後悔境界を持つアルゴリズムを設計する。 我々は,学習者が失った損失の数を観察することが許された場合に,バンディット設定にも同様の一階後悔が生じることを証明した。 これらは、最高のアームの損失と遅延にのみ依存する遅延設定の最初の境界である。 バンディット設定において損失以外の情報が観測されていない場合、ジマートとセルディンのアルゴリズム(2020年)の修正を通じて、我々は依然として後悔を証明することができる。 私たちの分析は、ドリフトに束縛された新しいバウンドにかかっており、1ラウンドのルックアヘッドを与えられるとアルゴリズムがどれだけうまく機能するかを測定します。

関連論文リスト

• Biased Dueling Bandits with Stochastic Delayed Feedback [6.167074802065416]
  遅延を伴う状況に対処するアルゴリズムを2つ提案する。 完全遅延分布情報を必要とする第1のアルゴリズムは,遅延のない場合の遅延帯域問題に対する最適後悔境界を達成できる。 第2のアルゴリズムは、分布が不明な状況に最適化されるが、遅延の期待値のみが利用可能である。
  論文  参考訳（メタデータ） (2024-08-26T19:49:12Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。 この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
  論文  参考訳（メタデータ） (2024-02-23T06:27:12Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays [24.998122268199797]
  本稿では,フィードバックが可変に遅延するバンディットのためのベスト・オブ・ボス・ワールドス・アルゴリズムを提案する。 我々のアルゴリズムは任意の過剰な遅延を許容し、$T$をオーダーすることができる。
  論文  参考訳（メタデータ） (2023-08-21T12:17:40Z)
• Delayed Feedback in Generalised Linear Bandits Revisited [5.349852254138085]
  一般化線形包帯における遅延報酬の現象を理論的に研究する。 遅延フィードバックに対する楽観的なアルゴリズムの自然な適応は、遅延に対するペナルティが地平線から独立であるような後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2022-07-21T23:35:01Z)
• Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts [53.579515853222986]
  時間分割リワード(TP-MAB)を用いたマルチアーメッド・バンディット(Multi-Armed Bandit)について検討する。 この設定は、プル後の有限時間スパン上で報酬が拡張されるケースに対する遅延フィードバックバンディットの自然な拡張である。 本稿では,TP-UCB-FRとTP-UCB-EWの2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-01T15:56:59Z)
• Nonstochastic Bandits with Composite Anonymous Feedback [41.38921728211769]
  本研究では,アクションの損失が直ちにプレイヤーに請求されない非確率的バンディット設定について検討する。 各ラウンドの最後にプレイヤーが観測した瞬間的な損失は、これまでプレイされたアクションの多くの損失成分の合計である。
  論文  参考訳（メタデータ） (2021-12-06T08:44:04Z)
• Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions [54.25616645675032]
  アルゴリズムが受信したフィードバックにランダムな遅延を伴うマルチアーマッド・バンドイット(MAB)問題について検討する。 報酬非依存の遅延設定は、報酬非依存の遅延設定と、報酬非依存の遅延設定に依存する可能性がある。 私たちの主な貢献は、それぞれの設定でほぼ最適に後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2021-06-04T12:26:06Z)
• Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
  静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。 我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。 最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
  論文  参考訳（メタデータ） (2020-12-07T08:23:08Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。 我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
  論文  参考訳（メタデータ） (2020-10-12T20:53:52Z)
• Stochastic bandits with arm-dependent delays [102.63128271054741]
  我々は、単純なUCBベースのアルゴリズムであるPatentBanditsを提案する。 問題に依存しない境界も問題に依存しない境界も、性能の低い境界も提供します。
  論文  参考訳（メタデータ） (2020-06-18T12:13:58Z)

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

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