論文の概要: Flickering Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2602.17315v1
• Date: Thu, 19 Feb 2026 12:24:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-20 15:21:29.025587
• Title: Flickering Multi-Armed Bandits
• Title（参考訳）: マルチアーマッドバンドのフリックリング
• Authors: Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen,
• Abstract要約: Flickering Multi-Armed Bandits (FMAB) は、利用可能なアーム(またはアクション)のセットを各ラウンドで変更できる新しいMABフレームワークである。 我々は、アームがノードであり、エージェントの動きが局所的に制限されるランダムグラフプロセスを用いて、制約付きで進化する可用性をモデル化する。 本アルゴリズムは,この問題クラスに対する情報理論的下界の整合性を確立することにより,ほぼ最適であることを示す。
• 参考スコア（独自算出の注目度）: 7.465238700168576
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce Flickering Multi-Armed Bandits (FMAB), a new MAB framework where the set of available arms (or actions) can change at each round, and the available set at any time may depend on the agent's previously selected arm. We model this constrained, evolving availability using random graph processes, where arms are nodes and the agent's movement is restricted to its local neighborhood. We analyze this problem under two random graph models: an i.i.d. Erdős--Rényi (ER) process and an Edge-Markovian process. We propose and analyze a two-phase algorithm that employs a lazy random walk for exploration to efficiently identify the optimal arm, followed by a navigation and commitment phase for exploitation. We establish high-probability and expected sublinear regret bounds for both graph settings. We show that the exploration cost of our algorithm is near-optimal by establishing a matching information-theoretic lower bound for this problem class, highlighting the fundamental cost of exploration under local-move constraints. We complement our theoretical guarantees with numerical simulations, including a scenario of a robotic ground vehicle scouting a disaster-affected region.
• Abstract（参考訳）: Flickering Multi-Armed Bandits (FMAB) は、利用可能なアーム(またはアクション)のセットが各ラウンドで変更可能な新しいMABフレームワークであり、いつでも利用可能なセットはエージェントが選択したアームに依存する可能性がある。 我々は、アームがノードであり、エージェントの動きが局所的に制限されるランダムグラフプロセスを用いて、制約付きで進化する可用性をモデル化する。 我々はこの問題を2つのランダムグラフモデル、すなわちエルデシュ=レーニ(ER)過程とエッジ-マルコフ過程で解析する。 本稿では,探索に遅延ランダムウォークを用い,最適なアームを効率よく同定する2相アルゴリズムの提案と解析を行った。 両グラフ設定に対して高い確率と期待されるサブ線形後悔境界を確立する。 本稿では,本アルゴリズムの探索コストが,局所移動制約下での探索の基本的なコストを浮き彫りにして,情報理論の下限の整合性を確立することにより,ほぼ最適であることを示す。 我々は,災害に遭った地域を偵察するロボット地上車両のシナリオを含む数値シミュレーションにより,我々の理論的保証を補完する。

関連論文リスト

• Semi-Parametric Batched Global Multi-Armed Bandits with Covariates [0.48342038441006807]
  マルチアームバンディット(MAB)フレームワークは、シーケンシャルな意思決定に広く使われているアプローチである。 本稿では,コパラメトリックと腕間の共有パラメータを持つバッチバンドの半パラメトリックフレームワークを提案する。 Batched Single-Index Dynamic binning and Successive arm elimination (BIDS) というアルゴリズムでは、バッチ化された逐次アームの除去戦略を採用している。
  論文  参考訳（メタデータ） (2025-03-01T17:23:55Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• Latency-Aware Contextual Bandit: Application to Cryo-EM Data Collection [23.51929492181581]
  本稿では,標準的なコンテキスト帯域幅問題を一般化した待ち時間対応のコンテキスト帯域幅フレームワークを提案する。 この設定では、学習者はコンテキストを観察し、選択されたサブセットによって決定される合計時間で、決定セットから複数のアームを選択することができる。 提案アルゴリズムは, 探索, エクスプロイト, 動作遅延のバランスを保ち, 最適平均回帰ポリシーに対する後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2024-10-17T00:44:50Z)
• Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
  提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。 本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
  論文  参考訳（メタデータ） (2021-12-08T02:20:18Z)
• PAC Best Arm Identification Under a Deadline [101.10352416022559]
  我々は、$(epsilon, delta)$-PACベストアーム識別について研究し、意思決定者は、アームプル(サンプル)の数を最小化しながら、少なくとも1 - delta$の確率で最適なアームを識別しなければならない。 この作業では、決定者はT$ラウンドの期限が与えられ、各ラウンドで、どのアームを引っ張るか、何回引っ張るかを適応的に選ぶことができる。 本稿では,この設定のための新しいアルゴリズムであるElastic Batch Racing (EBR)を提案する。
  論文  参考訳（メタデータ） (2021-06-06T19:48:32Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)

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

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