論文の概要: An LP-based Sampling Policy for Multi-Armed Bandits with Side-Observations and Stochastic Availability

• arxiv url: http://arxiv.org/abs/2603.26647v1
• Date: Fri, 27 Mar 2026 17:50:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-30 21:49:48.625166
• Title: An LP-based Sampling Policy for Multi-Armed Bandits with Side-Observations and Stochastic Availability
• Title（参考訳）: サイドオブザーバと確率的アベイラビリティを備えたマルチアーマッド帯域に対するLPベースサンプリングポリシー
• Authors: Ashutosh Soni, Peizhong Ju, Atilla Eryilmaz, Ness B. Shroff,
• Abstract要約: 本稿では,ネットワーク構造が関連する動作を横取り可能なマルチアーム・バンディット(MAB)問題について検討する。 我々は、アクションを未知の集合にリンクするために二部グラフを使用し、アクションを選択すると、それが関連付けられているすべての未知の観測結果が明らかになる。
• 参考スコア（独自算出の注目度）: 40.54677625701658
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the stochastic multi-armed bandit (MAB) problem where an underlying network structure enables side-observations across related actions. We use a bipartite graph to link actions to a set of unknowns, such that selecting an action reveals observations for all the unknowns it is connected to. While previous works rely on the assumption that all actions are permanently accessible, we investigate the more practical setting of stochastic availability, where the set of feasible actions (the "activation set") varies dynamically in each round. This framework models real-world systems with both structural dependencies and volatility, such as social networks where users provide side-information about their peers' preferences, yet are not always online to be queried. To address this challenge, we propose UCB-LP-A, a novel policy that leverages a Linear Programming (LP) approach to optimize exploration-exploitation trade-offs under stochastic availability. Unlike standard network bandit algorithms that assume constant access, UCB-LP-A computes an optimal sampling distribution over the realizable activation sets, ensuring that the necessary observations are gathered using only the currently active arms. We derive a theoretical upper bound on the regret of our policy, characterizing the impact of both the network structure and the activation probabilities. Finally, we demonstrate through numerical simulations that UCB-LP-A significantly outperforms existing heuristics that ignore either the side-information or the availability constraints.
• Abstract（参考訳）: 本稿では,ネットワーク構造が関連する動作の側方観測を可能にする確率的マルチアーム・バンディット(MAB)問題について検討する。 我々は、アクションを未知の集合にリンクするために二部グラフを使用し、アクションを選択すると、それが関連付けられているすべての未知の観測結果が明らかになる。 これまでの研究は、全てのアクションが永久にアクセス可能であるという仮定に依存していたが、より実践的な確率的可用性の設定について検討し、各ラウンドにおいて実行可能なアクションのセット(「アクティベーションセット」)が動的に変化する。 このフレームワークは、ソーシャルネットワークのような構造的依存関係とボラティリティの両方を持つ現実世界のシステムをモデル化する。 この課題に対処するために,線形プログラミング(LP)アプローチを利用して,確率的可用性下での探索・探索トレードオフを最適化する新しいポリシーである UCB-LP-A を提案する。 一定のアクセスを仮定する標準的なネットワーク帯域幅アルゴリズムとは異なり、UTB-LP-Aは実現可能なアクティベーションセット上の最適なサンプリング分布を計算し、現在のアクティブアームのみを使用して必要な観測を収集する。 我々は、ネットワーク構造とアクティベーション確率の両方の影響を特徴付ける、政策の後悔に基づく理論上の上限を導出する。 最後に,UCB-LP-Aは,情報・可用性の制約を無視する既存のヒューリスティックよりも優れていることを示す。

関連論文リスト

• Stochastic Encodings for Active Feature Acquisition [100.47043816019888]
  Active Feature Acquisitionは、インスタンスワイドでシーケンシャルな意思決定問題である。 目的は、テストインスタンスごとに独立して、現在の観測に基づいて計測する機能を動的に選択することである。 一般的なアプローチは強化学習(Reinforcement Learning)であり、トレーニングの困難を経験する。 我々は、教師付きで訓練された潜在変数モデルを導入し、潜在空間における観測不能な実現の可能性の多くにまたがる特徴を推論することで獲得する。
  論文  参考訳（メタデータ） (2025-08-03T23:48:46Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  提案するSEQUOIAは,動作空間に対する長期報酬を直接最適化するRLアルゴリズムである。 我々は,複数介入,経路制約,二部間マッチング,容量制約という,制約を伴う4つの新しいレスレス・バンディット問題に対して,SEQUOIAを実証的に検証した。
  論文  参考訳（メタデータ） (2025-03-01T21:25:21Z)
• Scalable Multi-Agent Offline Reinforcement Learning and the Role of Information [37.18643811339418]
  データセット収集とオフライン学習の両方にスケーラブルな新しいルーチンを提案する。 エージェントはまず、事前に特定された情報共有ネットワークと一貫性のある多様なデータセットを収集する。 提案手法は,FQIの教師あり学習段階における固有誤差を,共有情報と非共有情報との相互情報に限定することを可能にしている。
  論文  参考訳（メタデータ） (2025-02-16T20:28:42Z)
• Offline Learning for Combinatorial Multi-armed Bandits [56.96242764723241]
  Off-CMABはCMABの最初のオフライン学習フレームワークである。 Off-CMABは悲観的な報酬推定と解法を組み合わせる。 合成および実世界のデータセットの実験は、CLCBの優れた性能を強調している。
  論文  参考訳（メタデータ） (2025-01-31T16:56:18Z)
• Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraints [0.0]
  異種エージェントを用いた線形文脈帯域における保守的分散マルチタスク学習について述べる。 正確なコンテキストは不明で、エージェントが利用できるのはコンテキスト分布のみである。 提案アルゴリズムは,各ラウンドにおいて,制約を満たすためにプルーニングされた動作セットを構築する。 中央サーバを介してエージェント間での見積もりの同期共有を含む。
  論文  参考訳（メタデータ） (2024-01-21T18:43:55Z)

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

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