論文の概要: Delay as Payoff in MAB

• arxiv url: http://arxiv.org/abs/2408.15158v1
• Date: Tue, 27 Aug 2024 15:52:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-28 13:13:36.195715
• Title: Delay as Payoff in MAB
• Title（参考訳）: MABのペイオフとしての遅延
• Authors: Ofir Schlisselberg, Ido Cohen, Tal Lancewicki, Yishay Mansour,
• Abstract要約: エージェントが受信した支払いが遅延し、直接遅延の大きさに対応する古典的マルチアーム帯域幅問題(MAB)の変種について検討する。 当社の主なコントリビューションは、コストと報酬の設定の両方に関して、上と下の境界の厳格さです。 私たちの後悔は、コストシナリオと報酬シナリオの違いを強調し、コストシナリオの改善が報酬よりも重要であることを示すことです。
• 参考スコア（独自算出の注目度）: 40.65658965074464
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we investigate a variant of the classical stochastic Multi-armed Bandit (MAB) problem, where the payoff received by an agent (either cost or reward) is both delayed, and directly corresponds to the magnitude of the delay. This setting models faithfully many real world scenarios such as the time it takes for a data packet to traverse a network given a choice of route (where delay serves as the agent's cost); or a user's time spent on a web page given a choice of content (where delay serves as the agent's reward). Our main contributions are tight upper and lower bounds for both the cost and reward settings. For the case that delays serve as costs, which we are the first to consider, we prove optimal regret that scales as $\sum_{i:\Delta_i > 0}\frac{\log T}{\Delta_i} + d^*$, where $T$ is the maximal number of steps, $\Delta_i$ are the sub-optimality gaps and $d^*$ is the minimal expected delay amongst arms. For the case that delays serves as rewards, we show optimal regret of $\sum_{i:\Delta_i > 0}\frac{\log T}{\Delta_i} + \bar{d}$, where $\bar d$ is the second maximal expected delay. These improve over the regret in the general delay-dependent payoff setting, which scales as $\sum_{i:\Delta_i > 0}\frac{\log T}{\Delta_i} + D$, where $D$ is the maximum possible delay. Our regret bounds highlight the difference between the cost and reward scenarios, showing that the improvement in the cost scenario is more significant than for the reward. Finally, we accompany our theoretical results with an empirical evaluation.
• Abstract（参考訳）: 本稿では,従来の確率的マルチアームバンド問題 (MAB) の変種について検討し,エージェント(コストや報酬)の支払いが遅れており,遅延の程度と直接対応している。 この設定は、ルートを選択するのにデータパケットがネットワークを横断するのに要する時間(遅延がエージェントのコストとなる場所)や、コンテンツを選択するのにウェブページで費やす時間(遅延がエージェントの報酬となる場所)など、多くの現実のシナリオを忠実にモデル化する。 当社の主なコントリビューションは、コストと報酬の設定の両方に関して、上と下の境界の厳格さです。 ここでは、$T$はステップの最大数、$\Delta_i$はサブ最適ギャップ、$d^*$は腕の最小遅延である。 遅延が報酬となる場合、$\sum_{i:\Delta_i > 0}\frac{\log T}{\Delta_i} + \bar{d}$ の最適後悔を示す。 これは、一般的な遅延依存のペイオフ設定における後悔よりも改善され、$\sum_{i:\Delta_i > 0}\frac{\log T}{\Delta_i} + D$にスケールする。 私たちの後悔は、コストシナリオと報酬シナリオの違いを強調し、コストシナリオの改善が報酬よりも重要であることを示すことです。 最後に,実験的な評価とともに理論的結果に付随する。

関連論文リスト

• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  遅延フィードバックを伴うバンド凸最適化(BCO)。 我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。 提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
  論文  参考訳（メタデータ） (2024-02-14T13:08:26Z)
• A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback [25.68113242132723]
  本稿では,Zimmert と Seldin [2020] のアルゴリズムを,フィードバックの遅れによる逆方向の多重武装バンディットに対して修正したチューニングを行う。 我々は,時間的遅れのある設定において,ほぼ最適の相反的後悔の保証を同時に達成する。 また,任意の遅延の場合に対するアルゴリズムの拡張も提案する。
  論文  参考訳（メタデータ） (2022-06-29T20:49:45Z)
• Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback [67.63049551992816]
  エピソードマルコフ決定過程(MDP)におけるオンライン学習について検討した。 ほぼ最適の$sqrtK + D$ regret, where $K$ is the number of episodes, $D = sum_k=1K dk$ is the total delay。
  論文  参考訳（メタデータ） (2022-01-31T12:34:26Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret [144.6358229217845]
  エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
  論文  参考訳（メタデータ） (2021-04-22T17:20:48Z)
• Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
  オンライン凸最適化の問題点を未知の遅延で検討する。 まず、OGDの遅延変形を強凸関数に拡張する。 我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
  論文  参考訳（メタデータ） (2021-03-21T10:16:15Z)
• Learning Adversarial Markov Decision Processes with Delayed Feedback [45.86354980347581]
  私たちは、未知の移行、逆転的なコストの変動、制限のない遅延フィードバックを備えた典型的マルコフ決定プロセス(MDP)におけるオンライン学習を検討します。 本論文では,$widetilde O ( sqrtK + sqrtD )$ のほぼ最適高確率後悔を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-29T16:47:42Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。 我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
  論文  参考訳（メタデータ） (2020-10-12T20:53:52Z)

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

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