論文の概要: Pooling and Drift in Delayed Bandits

• arxiv url: http://arxiv.org/abs/2609.01761v2
• Date: Sun, 06 Sep 2026 22:38:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-09 22:37:20.341195
• Title: Pooling and Drift in Delayed Bandits
• Title（参考訳）: 遅延帯域におけるプーリングとドリフト
• Abstract要約: 推薦者は数秒でクリックし、数日で購入する。 K$アクションと$d$ラウンドの遅延により、この設定で知られている最高のレートは$widetildeO(sqrt(K+d)T)$ over $T$ラウンドである。 我々は、$d$のラウンドから正確に損失があったとしても、アルゴリズムが$(sqrtdEmin1+log J,T/d)$を逃すことはないことを示した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A system often has to act long before it learns whether the act worked: a recommender sees a click in seconds and a purchase in days. With $K$ actions and a delay of $d$ rounds, the best rate known for this setting is $\widetilde{O}(\sqrt{(K+d)T})$ over $T$ rounds, so a longer menu is always more expensive to learn from. It need not be: if the outcome depends on the action only through the state it produced, then one late outcome informs every action that could have produced the observed state, and the price is set by how many genuinely different states the actions produce rather than by how many actions there are. We measure this using an effective dimension $v_t$ between $1$ and the number of states, and prove $\widetilde{O}(\sqrt{(d+1)V\log K})$ for a rotating algorithm and $\widetilde{O}(\sqrt{V^{-}}+\sqrt{dT})$ for the single-copy algorithm used in practice, for any budget fixed in advance; merging similar states lowers the price further, at an explicit bias. Even when given the exact losses from $d$ rounds ago, no algorithm escapes $Ω(\sqrt{dE\min\{1+\log J,T/d\}})$, where $J$ counts the drifting directions and $E$ bounds how far losses move while the learner waits. On generated data, the state channel cuts regret by up to 79 percent against action-level weighting and, on the funnel family, by 32 to 68 percent against a tuned minimax-optimal method.
• Abstract（参考訳）: 推奨者は数秒でクリックし、何日かで購入する。 K$アクションと$d$ラウンドの遅延により、この設定で知られている最高のレートは$\widetilde{O}(\sqrt{(K+d)T})$ over $T$ラウンドである。 結果が、それが生成した状態を通してのみアクションに依存する場合、1つの遅れた結果が、観測された状態を生成する可能性のあるすべてのアクションを通知し、そのアクションが生成する真の異なる状態の数によって価格が設定される。 実効次元 $v_t$ と状態数を用いてこれを測定し、回転アルゴリズムに対して $\widetilde{O}(\sqrt{(d+1)V\log K})$ と、前もって固定された予算に対して実際に使用されるシングルコピーアルゴリズムに対して $\widetilde{O}(\sqrt{V^{-}}+\sqrt{dT})$ を証明した。 以前の$d$ラウンドから正確な損失が与えられたとしても、$J$はドリフト方向をカウントし、$E$は学習者が待機している間にどれだけの損失が動くかを示すような$Ω(\sqrt{dE\min\{1+\log J,T/d\}})$を逃れるアルゴリズムは存在しない。 生成されたデータでは、アクションレベルの重み付けに対して最大で79%の後悔を減らし、ファンネルファミリーでは、調整されたミニマックス最適化法に対して32～68%の後悔を減らします。

関連論文リスト

• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
  オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。 この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。 この設定のための最初のポリシー最適化アルゴリズムを紹介します。
  論文  参考訳（メタデータ） (2025-02-06T12:03:24Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• Communication Efficient Parallel Reinforcement Learning [34.77250498401055]
  我々は、$m$エージェントが$s$状態と$a$アクションを持つ$m$同一および独立環境と相互作用する問題を考える。 我々はエージェントが不適切なコミュニケーションラウンドで後悔を最小限に抑えるアルゴリズムを見つけることを目的としている。
  論文  参考訳（メタデータ） (2021-02-22T02:46:36Z)
• An Analysis of Frame-skipping in Reinforcement Learning [13.680685626360903]
  多くのAtariコンソールゲームでは、強化学習アルゴリズムが$d > 1$で実行する場合、かなり優れたポリシーを提供する。 我々は、同じアクションの$d$長のシーケンスに対するこの選択の一般的な制限である「アクション-繰り返し」に焦点を当てる。 この損失は、より小さなタスクの地平線によって学習がもたらされた利益によって相殺される可能性がある。
  論文  参考訳（メタデータ） (2021-02-07T04:59:09Z)

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

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