論文の概要: Contextual Linear Bandits with Delay as Payoff

• arxiv url: http://arxiv.org/abs/2502.12528v2
• Date: Thu, 20 Feb 2025 01:16:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-21 10:45:28.023415
• Title: Contextual Linear Bandits with Delay as Payoff
• Title（参考訳）: 納期が遅れたコンテキスト線形帯域
• Authors: Mengxiao Zhang, Yingfei Wang, Haipeng Luo,
• Abstract要約: コンテキスト線形帯域に対する遅延・アズ・ペイオフモデルについて検討する。 本稿では,標準の非遅延の場合と比較して,最大で$DDelta_maxlog T$の遅延オーバヘッドを持つ効率的なアルゴリズムを提案する。 ペイオフが損失である場合には、さらにバウンドの改善を示し、シュリッセルベルクらと同様の報酬と損失の分離を示す(2024年)。
• 参考スコア（独自算出の注目度）: 37.59998488833435
• License:
• Abstract: A recent work by Schlisselberg et al. (2024) studies a delay-as-payoff model for stochastic multi-armed bandits, where the payoff (either loss or reward) is delayed for a period that is proportional to the payoff itself. While this captures many real-world applications, the simple multi-armed bandit setting limits the practicality of their results. In this paper, we address this limitation by studying the delay-as-payoff model for contextual linear bandits. Specifically, we start from the case with a fixed action set and propose an efficient algorithm whose regret overhead compared to the standard no-delay case is at most $D\Delta_{\max}\log T$, where $T$ is the total horizon, $D$ is the maximum delay, and $\Delta_{\max}$ is the maximum suboptimality gap. When payoff is loss, we also show further improvement of the bound, demonstrating a separation between reward and loss similar to Schlisselberg et al. (2024). Contrary to standard linear bandit algorithms that construct least squares estimator and confidence ellipsoid, the main novelty of our algorithm is to apply a phased arm elimination procedure by only picking actions in a volumetric spanner of the action set, which addresses challenges arising from both payoff-dependent delays and large action sets. We further extend our results to the case with varying action sets by adopting the reduction from Hanna et al. (2023). Finally, we implement our algorithm and showcase its effectiveness and superior performance in experiments.
• Abstract（参考訳）: Schlisselberg et al (2024) による最近の研究は、確率的マルチアーム・バンディットに対する遅延・アズ・ペイオフモデル(英語版)を研究しており、このモデルでは、ペイオフ自体に比例する期間において、ペイオフ(損失または報酬)が遅延する。 これは現実世界のアプリケーションの多くをキャプチャするが、単純なマルチアームバンディット設定は結果の実用性を制限する。 本稿では,この制限を文脈線形帯域に対する遅延・アズ・ペイオフモデルを用いて検討する。 具体的には、固定されたアクションセットのケースから始め、標準の非遅延の場合と比較して遅延オーバヘッドが最大$D\Delta_{\max}\log T$で、$T$が全水平線、$D$が最大遅延、$\Delta_{\max}$が最大亜最適ギャップである効率的なアルゴリズムを提案する。 ペイオフが損失である場合には、さらにバウンドの改善を示し、Schlisselberg et al (2024)と同様の報酬と損失の分離を示す。 最小二乗推定器と信頼楕円体を構成する標準線形バンディットアルゴリズムとは対照的に,本アルゴリズムの主な新規性は,アクションセットのボリュームスパンナーでのみ動作を選択することで,フェーズドアームの除去手順を適用することであり,これはペイオフ依存遅延と大きなアクションセットの両方から生じる課題に対処する。 我々はさらに、Hanna et al (2023) からの還元を採用することで、様々なアクションセットで結果をさらに拡張する。 最後に,本アルゴリズムを実装し,その有効性と性能を実験で示す。

関連論文リスト

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits [29.097522376094624]
  そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。 我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
  論文  参考訳（メタデータ） (2022-10-25T19:13:20Z)
• Nonstochastic Bandits with Composite Anonymous Feedback [41.38921728211769]
  本研究では,アクションの損失が直ちにプレイヤーに請求されない非確率的バンディット設定について検討する。 各ラウンドの最後にプレイヤーが観測した瞬間的な損失は、これまでプレイされたアクションの多くの損失成分の合計である。
  論文  参考訳（メタデータ） (2021-12-06T08:44:04Z)
• Nonstochastic Bandits and Experts with Arm-Dependent Delays [17.272515865592542]
  遅延が時間と腕に依存するような遅延環境で,非確率的な盗賊や専門家について検討する。 私たちの分析では、ドリフトに縛られた小説にヒンジを付け、1ラウンドのルックアヘッドを与えられた場合、アルゴリズムがどれだけの精度で実行できるかを測定しました。
  論文  参考訳（メタデータ） (2021-11-02T13:36:11Z)
• Break your Bandit Routine with LSD Rewards: a Last Switch Dependent Analysis of Satiation and Seasonality [6.146046338698175]
  そこで本研究では,腕が最後に動作を切り替えて以降の時間経過によって,腕の期待される報酬が完全に決定される,新たな非定常バンディット問題を導入する。 我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。 我々はアルゴリズムを証明し、最適な非定常ポリシーに関してその後悔を証明した。
  論文  参考訳（メタデータ） (2021-10-22T14:53:13Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。 我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
  論文  参考訳（メタデータ） (2020-10-12T20:53:52Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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