Fugu-MT 論文翻訳(概要): Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit

論文の概要: Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit

arxiv url: http://arxiv.org/abs/2308.10238v3
Date: Wed, 15 Nov 2023 11:00:20 GMT
ステータス: 処理完了
システム内更新日: 2023-11-16 20:03:58.355699
Title: Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit
Title（参考訳）: マルチアーメッドバンドの実値組合せ純粋探索のためのトンプソンサンプリング
Authors: Shintaro Nakamura, Masashi Sugiyama
Abstract要約: 本稿では,マルチアームバンディット(R-CPE-MAB)問題の実測値について検討する。一般トンプソンサンプリング探索法(GenTS-Explore)と呼ばれるアルゴリズムを導入する。これは,アクションセットのサイズが指数関数的に$d$で大きい場合でも動作可能な,最初のアルゴリズムである。
参考スコア（独自算出の注目度）: 65.268245109828
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the real-valued combinatorial pure exploration of the multi-armed bandit (R-CPE-MAB) problem. In R-CPE-MAB, a player is given $d$ stochastic arms, and the reward of each arm $s\in\{1, \ldots, d\}$ follows an unknown distribution with mean $\mu_s$. In each time step, a player pulls a single arm and observes its reward. The player's goal is to identify the optimal \emph{action} $\boldsymbol{\pi}^{*} = \argmax_{\boldsymbol{\pi} \in \mathcal{A}} \boldsymbol{\mu}^{\top}\boldsymbol{\pi}$ from a finite-sized real-valued \emph{action set} $\mathcal{A}\subset \mathbb{R}^{d}$ with as few arm pulls as possible. Previous methods in the R-CPE-MAB assume that the size of the action set $\mathcal{A}$ is polynomial in $d$. We introduce an algorithm named the Generalized Thompson Sampling Explore (GenTS-Explore) algorithm, which is the first algorithm that can work even when the size of the action set is exponentially large in $d$. We also introduce a novel problem-dependent sample complexity lower bound of the R-CPE-MAB problem, and show that the GenTS-Explore algorithm achieves the optimal sample complexity up to a problem-dependent constant factor.
Abstract（参考訳）: 本稿では,マルチアームバンディット(R-CPE-MAB)問題の実測値について検討する。 R-CPE-MABでは、プレイヤーは確率的な腕を$d$与えられ、各アームの報酬は$s\in\{1, \ldots, d\}$が平均$\mu_s$の未知分布に従う。各タイムステップで、プレイヤーは片方の腕を引っ張り、その報酬を観察する。プレイヤーのゴールは、最適な \emph{action} $\boldsymbol{\pi}^{*} = \argmax_{\boldsymbol{\pi} \in \mathcal{A}} \boldsymbol{\mu}^{\top}\boldsymbol{\pi}$を有限サイズの実数値の \emph{action set} $\mathcal{A}\subset \mathbb{R}^{d}$から極小のアームプルで識別することである。 R-CPE-MAB の以前の方法では、アクションセット $\mathcal{A}$ のサイズは$d$ の多項式である。一般トンプソンサンプリング探索法(GenTS-Explore)と呼ばれるアルゴリズムを導入する。これはアクションセットのサイズが指数関数的に$d$で大きい場合でも動作する最初のアルゴリズムである。また,R-CPE-MAB問題に対して,新たな問題依存型サンプル複雑性を低い境界で導入し,GenTS-Exploreアルゴリズムが問題依存定数係数まで最適なサンプル複雑性を実現することを示す。

関連論文リスト

Optimal Exploration is no harder than Thompson Sampling [14.726673043806391]
a pure exploration linear bandit problem to return $argmax_zin mathcalZ ztoptheta_ast with $xtoptheta_ast with $xin mathcalXsubset mathbbRd$。この複雑さは、後続サンプリングとargmaxオラクルへのアクセスを必要とするだけであり、$mathcalZ$を列挙する必要がない、後悔の最小化のために人気で単純なトンプソンサンプリングと矛盾する。
論文参考訳（メタデータ） (2023-10-09T18:21:39Z)
Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文参考訳（メタデータ） (2023-02-07T02:22:31Z)
Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文参考訳（メタデータ） (2022-10-05T22:52:00Z)
On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-02-13T10:54:52Z)
Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-22T05:00:13Z)
Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-17T22:32:19Z)
Combinatorial Pure Exploration with Full-Bandit or Partial Linear Feedback [18.29738891417779]
フルバンドフィードバック(CPE-BL)による純粋探索の問題点を最初に研究する。 CPE-BLでは、アクションのプル$x$は、$M_xtheta $を期待してランダムフィードバックベクトルを報告し、mathbbRd$の$M_xは、$x$の変換行列であり、$x$に関連するランダム(おそらく非線形)報酬を得る。 CPE-PLでは,限られたフィードバック,一般報酬関数,行動空間を同時に扱う最初のエムタイムアルゴリズムを開発した。
論文参考訳（メタデータ） (2020-06-14T13:59:59Z)
Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-13T05:00:01Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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