論文の概要: Combinatorial Pure Exploration with Full-Bandit or Partial Linear
Feedback
- arxiv url: http://arxiv.org/abs/2006.07905v2
- Date: Tue, 15 Dec 2020 05:59:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 10:00:34.859265
- Title: Combinatorial Pure Exploration with Full-Bandit or Partial Linear
Feedback
- Title（参考訳）: 全帯域または部分線形フィードバックによる組合せ純粋探索
- Authors: Yihan Du, Yuko Kuroki, Wei Chen
- Abstract要約: フルバンドフィードバック(CPE-BL)による純粋探索の問題点を最初に研究する。
CPE-BLでは、アクションのプル$x$は、$M_xtheta $を期待してランダムフィードバックベクトルを報告し、mathbbRd$の$M_xは、$x$の変換行列であり、$x$に関連するランダム(おそらく非線形)報酬を得る。
CPE-PLでは,限られたフィードバック,一般報酬関数,行動空間を同時に扱う最初のエムタイムアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 18.29738891417779
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we first study the problem of combinatorial pure exploration
with full-bandit feedback (CPE-BL), where a learner is given a combinatorial
action space $\mathcal{X} \subseteq \{0,1\}^d$, and in each round the learner
pulls an action $x \in \mathcal{X}$ and receives a random reward with
expectation $x^{\top} \theta$, with $\theta \in \mathbb{R}^d$ a latent and
unknown environment vector. The objective is to identify the optimal action
with the highest expected reward, using as few samples as possible. For CPE-BL,
we design the first {\em polynomial-time adaptive} algorithm, whose sample
complexity matches the lower bound (within a logarithmic factor) for a family
of instances and has a light dependence of $\Delta_{\min}$ (the smallest gap
between the optimal action and sub-optimal actions). Furthermore, we propose a
novel generalization of CPE-BL with flexible feedback structures, called
combinatorial pure exploration with partial linear feedback (CPE-PL), which
encompasses several families of sub-problems including full-bandit feedback,
semi-bandit feedback, partial feedback and nonlinear reward functions. In
CPE-PL, each pull of action $x$ reports a random feedback vector with
expectation of $M_{x} \theta $, where $M_x \in \mathbb{R}^{m_x \times d}$ is a
transformation matrix for $x$, and gains a random (possibly nonlinear) reward
related to $x$. For CPE-PL, we develop the first {\em polynomial-time}
algorithm, which simultaneously addresses limited feedback, general reward
function and combinatorial action space, and provide its sample complexity
analysis. Our empirical evaluation demonstrates that our algorithms run orders
of magnitude faster than the existing ones, and our CPE-BL algorithm is robust
across different $\Delta_{\min}$ settings while our CPE-PL algorithm is the
only one returning correct answers for nonlinear reward functions.
- Abstract（参考訳）: 本稿では,まず,学習者が組合せ作用空間 $\mathcal{x} \subseteq \{0,1\}^d$ を与えられ,各ラウンドにおいて,学習者がアクション $x \in \mathcal{x}$ をプルし,期待値 $x^{\top} \theta$, with $\theta \in \mathbb{r}^d$ a latent and unknown environment vector でランダム報酬を受ける,完全帯域フィードバック (cpe-bl) による組合せ純粋探索の問題を研究する。
目的は、できるだけ少数のサンプルを使用して、最も期待された報酬で最適なアクションを特定することである。
cpe-blでは、サンプル複雑性がインスタンス群の下限(対数係数を含む)と一致し、$\delta_{\min}$(最適アクションとサブ最適アクションの間の最小のギャップ)の光依存性を持つ最初の {\em polynomial-time adaptive}アルゴリズムを設計する。
さらに,CPE-BLのフレキシブルなフィードバック構造を持つ新たな一般化として,完全帯域フィードバック,半帯域フィードバック,部分フィードバック,非線形報酬関数を含むいくつかのサブプロブレムを含む,線形線形フィードバックを用いた組合せ純粋探索(CPE-PL)を提案する。
CPE-PL では、各アクション $x$ は、$M_{x} \theta $ を期待してランダムなフィードバックベクトルを報告し、$M_x \in \mathbb{R}^{m_x \times d}$ は$x$ の変換行列であり、$x$ に関連するランダムな(おそらく非線形な)報酬を得る。
cpe-plでは,限られたフィードバック,一般報酬関数,組合せ作用空間を同時に処理し,そのサンプル複雑性解析を提供する,最初の {\em polynomial-time}アルゴリズムを開発した。
我々のCPE-PLアルゴリズムは、非線形報酬関数に対して正しい答えを返す唯一のアルゴリズムである一方、我々のCPE-BLアルゴリズムは、異なる$\Delta_{\min}$設定に対して堅牢である。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Thompson Sampling for Real-Valued Combinatorial Pure Exploration of
Multi-Armed Bandit [65.268245109828]
本稿では,マルチアームバンディット(R-CPE-MAB)問題の実測値について検討する。
一般トンプソンサンプリング探索法(GenTS-Explore)と呼ばれるアルゴリズムを導入する。これは,アクションセットのサイズが指数関数的に$d$で大きい場合でも動作可能な,最初のアルゴリズムである。
論文 参考訳（メタデータ） (2023-08-20T11:56:02Z) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳（メタデータ） (2023-03-17T17:53:28Z) - Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility
Amortizations in Repeated Rankings [9.066817876491053]
我々は,生産者側の個々人の露出不公平さを最小限に抑えつつ,消費者側の実用性を最大化する一連のランキングを計算することの課題を考える。
幾何的対象 (polytope) と呼ばれる多面体(polytope) を導入し、その点が位置ベースモデルに対する全ての達成可能なアイテムの露出を表す。
提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から,線形あるいは二次的なプログラミングベースラインと比較した。
我々の解は、BvN分解で達成された$(n-1)2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
論文 参考訳（メタデータ） (2022-02-07T14:43:35Z) - Reward-Free Model-Based Reinforcement Learning with Linear Function
Approximation [92.99933928528797]
エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。
計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。
任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
論文 参考訳（メタデータ） (2021-10-12T23:03:58Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。