論文の概要: Influential Bandits: Pulling an Arm May Change the Environment

• arxiv url: http://arxiv.org/abs/2504.08200v1
• Date: Fri, 11 Apr 2025 02:05:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-14 14:19:52.916510
• Title: Influential Bandits: Pulling an Arm May Change the Environment
• Title（参考訳）: 腕を引っ張ると環境が変わるかも
• Authors: Ryoma Sato, Shinji Ito,
• Abstract要約: 現実世界のアプリケーションは、しばしば非定常環境と武器間の相互依存を含む。 本稿では,未知の,対称な正の半定値相互作用行列による腕間相互作用をモデル化する,影響力のあるバンドイット問題を提案する。 我々は,損失ダイナミクスの構造に合わせて,低信頼境界(LCB)推定器に基づく新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 44.71145269686588
• License:
• Abstract: While classical formulations of multi-armed bandit problems assume that each arm's reward is independent and stationary, real-world applications often involve non-stationary environments and interdependencies between arms. In particular, selecting one arm may influence the future rewards of other arms, a scenario not adequately captured by existing models such as rotting bandits or restless bandits. To address this limitation, we propose the influential bandit problem, which models inter-arm interactions through an unknown, symmetric, positive semi-definite interaction matrix that governs the dynamics of arm losses. We formally define this problem and establish two regret lower bounds, including a superlinear $\Omega(T^2 / \log^2 T)$ bound for the standard UCB algorithm and an algorithm-independent $\Omega(T)$ bound, which highlight the inherent difficulty of the setting. We then introduce a new algorithm based on a lower confidence bound (LCB) estimator tailored to the structure of the loss dynamics. Under mild assumptions, our algorithm achieves a regret of $O(KT \log T)$, which is nearly optimal in terms of its dependence on the time horizon. The algorithm is simple to implement and computationally efficient. Empirical evaluations on both synthetic and real-world datasets demonstrate the presence of inter-arm influence and confirm the superior performance of our method compared to conventional bandit algorithms.
• Abstract（参考訳）: 古典的なマルチアームバンディット問題の定式化は、各アームの報酬が独立で定常的であると仮定するが、現実の応用は、しばしば非定常環境とアーム間の相互依存を含む。 特に、一方の腕を選択することは、他の腕の将来の報酬に影響しうるが、これは、腐った包帯やレスレスト・バンディットのような既存のモデルによって適切に捉えられていないシナリオである。 この制限に対処するために、未知の対称な正の半定値相互作用行列を通して腕間の相互作用をモデル化し、腕の損失のダイナミクスを制御した、影響力のあるバンドイット問題を提案する。 我々はこの問題を正式に定義し、標準 UCB アルゴリズムに対する超線形 $\Omega(T^2 / \log^2 T)$bound とアルゴリズムに依存しない $\Omega(T)$bound という2つの後悔すべき下界を確立し、設定の固有の困難さを強調する。 次に、損失ダイナミクスの構造に合わせて、低信頼境界(LCB)推定器に基づく新しいアルゴリズムを導入する。 軽微な仮定の下では、我々のアルゴリズムは、時間的地平線に依存する点でほぼ最適である$O(KT \log T)$を後悔する。 このアルゴリズムは実装が簡単で、計算効率が良い。 人工と実世界の両方のデータセットに対する実証的な評価は、武器間影響の存在を示し、従来のバンディットアルゴリズムと比較して、提案手法の優れた性能を実証する。

関連論文リスト

• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Online Clustering of Bandits with Misspecified User Models [42.56440072468658]
  コンテキスト線形バンディット(Contextual linear bandit)は、与えられた腕の特徴を学習エージェントが各ラウンドで選択し、長期の累積報酬を最大化するオンライン学習問題である。 バンディットのクラスタリング(CB)と呼ばれる一連の研究は、ユーザの好みに対する協調効果を利用しており、古典的な線形バンディットアルゴリズムよりも大幅に改善されている。 本稿では,不特定ユーザモデル (CBMUM) による盗賊のクラスタリングに関する重要な問題を初めて提示する。 モデル誤特定による不正確なユーザの選好推定と誤クラスタリングを両立できる頑健なCBアルゴリズムRCLUMBとRCLUMBを考案した。
  論文  参考訳（メタデータ） (2023-10-04T10:40:50Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Piecewise-Stationary Multi-Objective Multi-Armed Bandit with Application to Joint Communications and Sensing [7.0997346625024]
  本稿では,この問題を解決するために,変化検出を用いた汎用上信頼境界(UCB)に基づくアルゴリズムを提案する。 また,統合通信・センシングシステムにおけるエネルギー効率のよい波形設計問題を玩具の例として定式化する。
  論文  参考訳（メタデータ） (2023-02-10T14:10:14Z)
• Stochastic Rising Bandits [40.32303434592863]
  本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。 この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2022-12-07T17:30:45Z)
• Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
  最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。 我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。 鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
  論文  参考訳（メタデータ） (2021-01-30T21:51:47Z)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
  我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。 本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
  論文  参考訳（メタデータ） (2020-11-05T05:16:04Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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