論文の概要: Understanding the stochastic dynamics of sequential decision-making
processes: A path-integral analysis of multi-armed bandits
- arxiv url: http://arxiv.org/abs/2208.06245v2
- Date: Sat, 10 Jun 2023 13:06:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-14 02:40:09.770696
- Title: Understanding the stochastic dynamics of sequential decision-making
processes: A path-integral analysis of multi-armed bandits
- Title（参考訳）: 逐次意思決定過程の確率的ダイナミクスの理解:多武装バンディットの経路積分解析
- Authors: Bo Li and Chi Ho Yeung
- Abstract要約: マルチアームバンディットモデル(MAB)は、不確実な環境で意思決定を研究する最も一般的なモデルの一つである。
本稿では,MABモデルの解析に統計物理学の手法を用いる。
- 参考スコア（独自算出の注目度）: 7.05949591248206
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The multi-armed bandit (MAB) model is one of the most classical models to
study decision-making in an uncertain environment. In this model, a player
chooses one of $K$ possible arms of a bandit machine to play at each time step,
where the corresponding arm returns a random reward to the player, potentially
from a specific unknown distribution. The target of the player is to collect as
many rewards as possible during the process. Despite its simplicity, the MAB
model offers an excellent playground for studying the trade-off between
exploration versus exploitation and designing effective algorithms for
sequential decision-making under uncertainty. Although many asymptotically
optimal algorithms have been established, the finite-time behaviors of the
stochastic dynamics of the MAB model appear much more challenging to analyze,
due to the intertwine between the decision-making and the rewards being
collected. In this paper, we employ techniques in statistical physics to
analyze the MAB model, which facilitates the characterization of the
distribution of cumulative regrets at a finite short time, the central quantity
of interest in an MAB algorithm, as well as the intricate dynamical behaviors
of the model. Our analytical results, in good agreement with simulations, point
to the emergence of an interesting multimodal regret distribution, with large
regrets resulting from excess exploitation of sub-optimal arms due to an
initial unlucky output from the optimal one.
- Abstract（参考訳）: マルチアームバンディット(MAB)モデルは、不確実な環境で意思決定を研究する最も古典的なモデルの一つである。
このモデルでは、プレイヤーは各時間ステップで演奏するバンディットマシンの$k$のアームのいずれかを選択し、対応するアームは特定の未知の分布からプレイヤーにランダムな報酬を返す。
プレイヤーの目標は、プロセス中にできるだけ多くの報酬を集めることである。
その単純さにもかかわらず、MABモデルは、探究と搾取の間のトレードオフを研究し、不確実性の下でシーケンシャルな意思決定のための効果的なアルゴリズムを設計するための優れた遊び場を提供する。
多くの漸近的最適アルゴリズムが確立されているが、決定と報酬の相互関係のため、MABモデルの確率力学の有限時間挙動はより解析が困難であるように見える。
本稿では,統計物理学の手法を用いてmabモデルの解析を行い,有限短時間における累積的後悔の分布,mabアルゴリズムに対する関心の中心量,およびモデルの複雑な動的挙動のキャラクタリゼーションを容易にする。
シミュレーションとよく一致した解析結果から, 最適アームからの初回不運な出力により, サブ最適アームが過剰に活用されたことによる大きな後悔が, 興味深いマルチモーダル後悔分布の出現を示唆する。
関連論文リスト
- A Bandit Approach with Evolutionary Operators for Model Selection [0.4604003661048266]
この研究は、モデル選択を無限武装のバンディット問題、すなわち意思決定者が無限数の固定された選択のうちの1つを反復的に選択する問題として定式化する。
アームは、モデルの部分的なトレーニングに対応するアームをトレーニングし、選択するための機械学習モデルである(リソース割り当て)。
本稿では,Audiber らによって導入された UCB-E bandit アルゴリズムに,進化的アルゴリズムからの演算子を組み込んだ Mutant-UCB アルゴリズムを提案する。
3つのオープンソース画像分類データセットで実施されたテストは、この新しい組み合わせ手法の妥当性を証明し、状態よりも優れている。
論文 参考訳（メタデータ） (2024-02-07T08:01:45Z) - On Least Square Estimation in Softmax Gating Mixture of Experts [78.3687645289918]
決定論的MoEモデルに基づく最小二乗推定器(LSE)の性能について検討する。
我々は,多種多様な専門家関数の収束挙動を特徴付けるために,強い識別可能性という条件を確立する。
本研究は,専門家の選択に重要な意味を持つ。
論文 参考訳（メタデータ） (2024-02-05T12:31:18Z) - ShuttleSHAP: A Turn-Based Feature Attribution Approach for Analyzing
Forecasting Models in Badminton [52.21869064818728]
バドミントンにおけるプレイヤー戦術予測のための深層学習アプローチは、部分的にはラリープレイヤの相互作用に関する効果的な推論に起因する有望なパフォーマンスを示している。
本稿では,Shapley値の変量に基づいてバドミントンにおける予測モデルを解析するためのターンベース特徴属性手法であるShuttleSHAPを提案する。
論文 参考訳（メタデータ） (2023-12-18T05:37:51Z) - Let's reward step by step: Step-Level reward model as the Navigators for
Reasoning [64.27898739929734]
Process-Supervised Reward Model (PRM)は、トレーニングフェーズ中にステップバイステップのフィードバックをLLMに提供する。
LLMの探索経路を最適化するために,PRMからのステップレベルのフィードバックを応用した欲求探索アルゴリズムを提案する。
提案手法の汎用性を探るため,コーディングタスクのステップレベル報酬データセットを自動生成する手法を開発し,コード生成タスクにおける同様の性能向上を観察する。
論文 参考訳（メタデータ） (2023-10-16T05:21:50Z) - Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。
我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。
問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
論文 参考訳（メタデータ） (2023-01-18T00:53:46Z) - Exploration in Model-based Reinforcement Learning with Randomized Reward [40.87376174638752]
我々は、カーネル化線形レギュレータ(KNR)モデルの下では、報酬ランダム化が部分的最適化を保証することを示す。
さらに、我々の理論を一般化関数近似に拡張し、報酬ランダム化の条件を特定して、確実に効率的に探索する。
論文 参考訳（メタデータ） (2023-01-09T01:50:55Z) - Sample Efficient Reinforcement Learning via Model-Ensemble Exploration
and Exploitation [3.728946517493471]
MEEEは楽観的な探索と重み付けによる搾取からなるモデルアンサンブル法である。
我々の手法は、特にサンプル複雑性において、他のモデルフリーおよびモデルベース最先端手法よりも優れています。
論文 参考訳（メタデータ） (2021-07-05T07:18:20Z) - Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。
このアプローチは多くの実装と最適化の課題をもたらします。
提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
論文 参考訳（メタデータ） (2021-03-18T14:26:26Z) - Stein Variational Model Predictive Control [130.60527864489168]
不確実性の下での意思決定は、現実の自律システムにとって極めて重要である。
モデル予測制御 (MPC) 法は, 複雑な分布を扱う場合, 適用範囲が限られている。
この枠組みが、挑戦的で非最適な制御問題における計画の成功に繋がることを示す。
論文 参考訳（メタデータ） (2020-11-15T22:36:59Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。