論文の概要: Combinatorial Pure Exploration with Bottleneck Reward Function and its
Extension to General Reward Functions
- arxiv url: http://arxiv.org/abs/2102.12094v1
- Date: Wed, 24 Feb 2021 06:47:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-25 14:41:30.587329
- Title: Combinatorial Pure Exploration with Bottleneck Reward Function and its
Extension to General Reward Functions
- Title（参考訳）: Bottleneck Reward関数を用いた組合せ純粋探索と一般Reward関数への拡張
- Authors: Yihan Du, Yuko Kuroki, Wei Chen
- Abstract要約: ボトルネック報酬関数 (CPE-B) を用いたコンビネーションピュア探索問題について, 一定の信頼性と固定予算設定の下で検討する。
固定信頼と固定バジェットのアルゴリズムを両立させ,固定信頼設定のサンプル複雑性を低く設定する。
さらに、CPE-Bを一般報酬関数(CPE-G)に拡張し、非自明なサンプル複雑性を持つ一般非線形報酬関数に対する最初の固定信頼アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 13.982295536546728
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study the Combinatorial Pure Exploration problem with the
bottleneck reward function (CPE-B) under the fixed-confidence and fixed-budget
settings. In CPE-B, given a set of base arms and a collection of subsets of
base arms (super arms) following certain combinatorial constraint, a learner
sequentially plays (samples) a base arm and observes its random outcome, with
the objective of finding the optimal super arm that maximizes its bottleneck
value, defined as the minimum expected value among the base arms contained in
the super arm. CPE-B captures a variety of practical scenarios such as network
routing in communication networks, but it cannot be solved by the existing CPE
algorithms since most of them assumed linear reward functions. For CPE-B, we
present both fixed-confidence and fixed-budget algorithms, and provide the
sample complexity lower bound for the fixed-confidence setting, which implies
that our algorithms match the lower bound (within a logarithmic factor) for a
broad family of instances. In addition, we extend CPE-B to general reward
functions (CPE-G) and propose the first fixed-confidence algorithm for general
non-linear reward functions with non-trivial sample complexity. Our
experimental results on the top-$k$, path and matching instances demonstrate
the empirical superiority of our proposed algorithms over the baselines.
- Abstract（参考訳）: 本稿では,固定信頼度と固定予算設定の下で,ボトルネック報酬関数(CPE-B)を用いた組合せ純粋探索問題について検討する。
CPE-Bでは、一定の組合せ制約に従ったベースアームのセットとベースアーム(スーパーアーム)のサブセットを与えられた場合、学習者はベースアームを順次(サンプル)演奏し、そのランダムな結果を観察し、スーパーアームに含まれるベースアームの最小期待値として定義されたボトルネック値を最大化する最適なスーパーアームを見つけることを目的とする。
CPE-Bは、通信ネットワークにおけるネットワークルーティングのような様々な実践シナリオをキャプチャするが、その多くは線形報酬関数を仮定しているため、既存のCPEアルゴリズムでは解決できない。
CPE-Bの場合、固定信頼度と固定予算度の両方のアルゴリズムを提示し、固定信頼度設定のサンプル複雑性を低くすることで、我々のアルゴリズムが幅広いインスタンスの下位境界(対数係数)と一致することを示唆する。
さらに、CPE-Bを一般報酬関数(CPE-G)に拡張し、非自明なサンプル複雑性を持つ一般非線形報酬関数に対する最初の固定信頼アルゴリズムを提案する。
提案したアルゴリズムがベースラインよりも経験的優位性を示すため, 上位$k, path, matching インスタンスに関する実験結果を得た。
関連論文リスト
- Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。
我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。
本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文 参考訳（メタデータ） (2024-02-02T13:31:24Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed
Bandit [65.268245109828]
このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。
CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。
提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
論文 参考訳（メタデータ） (2023-10-24T09:47:32Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳（メタデータ） (2023-07-08T15:41:48Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - On Reward-Free RL with Kernel and Neural Function Approximations:
Single-Agent MDP and Markov Game [140.19656665344917]
エージェントが事前に特定された報酬関数を使わずに環境を徹底的に探索することを目的とした報酬のないRL問題について検討する。
関数近似の文脈でこの問題に取り組み、強力な関数近似器を活用する。
我々は、カーネルとニューラルファンクション近似器を用いた、証明可能な効率の良い報酬なしRLアルゴリズムを確立した。
論文 参考訳（メタデータ） (2021-10-19T07:26:33Z) - Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。
我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。
両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
論文 参考訳（メタデータ） (2021-10-05T18:02:10Z) - Provably Efficient Reward-Agnostic Navigation with Linear Value
Iteration [143.43658264904863]
我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。
そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
論文 参考訳（メタデータ） (2020-08-18T04:34:21Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。