論文の概要: Congested Bandits: Optimal Routing via Short-term Resets

• arxiv url: http://arxiv.org/abs/2301.09251v1
• Date: Mon, 23 Jan 2023 03:11:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-24 14:21:44.991775
• Title: Congested Bandits: Optimal Routing via Short-term Resets
• Title（参考訳）: 混雑帯域:短期リセットによる最適ルーティング
• Authors: Pranjal Awasthi, Kush Bhatia, Sreenivas Gollapudi, Kostas Kollias
• Abstract要約: 本研究では,過去の演奏回数に応じて各腕の報奨が許される「混雑バンド」の問題について検討する。 UCBスタイルのアルゴリズムを提案し、そのポリシーの後悔は$tildeO(sqrtK Delta T)$であることを示す。 線形コンテキスト的帯域設定では,最小二乗プランナを反復的に用いたアルゴリズムが,ポリシー後悔の$tildeO(sqrtdT + Delta)$を達成している。
• 参考スコア（独自算出の注目度）: 30.892724364965
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For traffic routing platforms, the choice of which route to recommend to a user depends on the congestion on these routes -- indeed, an individual's utility depends on the number of people using the recommended route at that instance. Motivated by this, we introduce the problem of Congested Bandits where each arm's reward is allowed to depend on the number of times it was played in the past $\Delta$ timesteps. This dependence on past history of actions leads to a dynamical system where an algorithm's present choices also affect its future pay-offs, and requires an algorithm to plan for this. We study the congestion aware formulation in the multi-armed bandit (MAB) setup and in the contextual bandit setup with linear rewards. For the multi-armed setup, we propose a UCB style algorithm and show that its policy regret scales as $\tilde{O}(\sqrt{K \Delta T})$. For the linear contextual bandit setup, our algorithm, based on an iterative least squares planner, achieves policy regret $\tilde{O}(\sqrt{dT} + \Delta)$. From an experimental standpoint, we corroborate the no-regret properties of our algorithms via a simulation study.
• Abstract（参考訳）: トラフィックルーティングプラットフォームでは、ユーザに推奨するルートの選択は、これらのルートの混雑に依存する。 そこで我々は,過去の$$$Delta$のタイムステップにおいて,各腕の報酬が演奏された回数に依存するという,混雑バンドの問題を紹介した。 この過去のアクションの履歴への依存は、アルゴリズムの現在の選択が将来のペイオフにも影響を及ぼす動的システムへとつながり、そのためにはアルゴリズムが必要となる。 本研究では,マルチアームバンディット(mab)設定と文脈バンディット設定における混雑を考慮した定式化について線形報酬を用いて検討した。 マルチアーム設定のために,UCBスタイルのアルゴリズムを提案し,そのポリシーの後悔は$\tilde{O}(\sqrt{K \Delta T})$であることを示す。 線形文脈帯域設定では、反復最小二乗プランナーに基づくアルゴリズムは、ポリシー後悔を$\tilde{O}(\sqrt{dT} + \Delta)$とする。 実験的な観点からは、シミュレーション研究を通じてアルゴリズムの非回帰特性を補足する。

関連論文リスト

• Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
  FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。 われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。 我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
  論文  参考訳（メタデータ） (2024-04-09T04:45:18Z)
• Stochastic Rising Bandits [40.32303434592863]
  本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。 この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2022-12-07T17:30:45Z)
• Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret [34.44347218903429]
  マルチアームバンディット設定は、最近非定常状態において研究されている。 各アクションの平均的なペイオフは、前回のプレイ以来のラウンド数の増加しない機能である。 我々は,我々のアルゴリズムがサブ線形後悔を伴う帯域幅アルゴリズムにどのように変換されるかを示す。
  論文  参考訳（メタデータ） (2022-05-29T23:55:36Z)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Modeling Attrition in Recommender Systems with Departing Bandits [84.85560764274399]
  政策に依存した地平線を捉えた新しいマルチアームバンディット構成を提案する。 まず、全てのユーザが同じタイプを共有しているケースに対処し、最近の UCB ベースのアルゴリズムが最適であることを実証する。 次に、ユーザが2つのタイプに分けられる、より困難なケースを前進させます。
  論文  参考訳（メタデータ） (2022-03-25T02:30:54Z)
• 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)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
  我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。 我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
  論文  参考訳（メタデータ） (2020-02-19T15:41:18Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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