論文の概要: Combinatorial Pure Exploration of Multi-Armed Bandit with a Real Number
Action Class
- arxiv url: http://arxiv.org/abs/2306.09202v1
- Date: Thu, 15 Jun 2023 15:37:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-16 14:18:23.178771
- Title: Combinatorial Pure Exploration of Multi-Armed Bandit with a Real Number
Action Class
- Title（参考訳）: 実数アクションクラスによる多腕バンディットの組合せ的純粋探索
- Authors: Shintaro Nakamura and Masashi Sugiyama
- Abstract要約: マルチアーム・バンディット・セッティング(MAB)における純粋探査(CPE)について検討する。
プレイヤーは、theimphaction class $mathcalA$からthetimal emphaction $boldpi*$を見つけたいと思っています。
我々は,R-CPE-MABに対する,我々の複雑性に対する試料の上限と,アクションクラスに依存した下限を示す。
- 参考スコア（独自算出の注目度）: 91.3755431537592
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The combinatorial pure exploration (CPE) in the stochastic multi-armed bandit
setting (MAB) is a well-studied online decision-making problem: A player wants
to find the optimal \emph{action} $\boldsymbol{\pi}^*$ from \emph{action class}
$\mathcal{A}$, which is a collection of subsets of arms with certain
combinatorial structures. Though CPE can represent many combinatorial
structures such as paths, matching, and spanning trees, most existing works
focus only on binary action class $\mathcal{A}\subseteq\{0, 1\}^d$ for some
positive integer $d$. This binary formulation excludes important problems such
as the optimal transport, knapsack, and production planning problems. To
overcome this limitation, we extend the binary formulation to real,
$\mathcal{A}\subseteq\mathbb{R}^d$, and propose a new algorithm. The only
assumption we make is that the number of actions in $\mathcal{A}$ is polynomial
in $d$. We show an upper bound of the sample complexity for our algorithm and
the action class-dependent lower bound for R-CPE-MAB, by introducing a quantity
that characterizes the problem's difficulty, which is a generalization of the
notion \emph{width} introduced in Chen et al.[2014].
- Abstract（参考訳）: 確率的多腕バンディット設定(英語版) (mab) におけるコンビネーション純粋探索 (cpe) はよく研究されたオンライン意思決定問題である: プレイヤーは特定のコンビネート構造を持つ腕の部分集合である \emph{action} $\boldsymbol{\pi}^*$ from \emph{action class} $\mathcal{a}$ を求める。
CPEはパス、マッチング、スパンニングツリーなどの多くの組合せ構造を表現できるが、既存の作業の多くは、ある正の整数 $d$ に対して、バイナリアクションクラス $\mathcal{A}\subseteq\{0, 1\}^d$ にのみフォーカスする。
この二項定式化は、最適輸送、ナップサック、生産計画といった重要な問題を排除する。
この制限を克服するために、二項式を real, $\mathcal{a}\subseteq\mathbb{r}^d$ に拡張し、新しいアルゴリズムを提案する。
唯一の仮定は、$\mathcal{A}$のアクションの数は$d$の多項式であるということです。
本稿では,提案アルゴリズムにおけるサンプル複雑性とR-CPE-MABに対する作用クラス依存下界の上限について,Chenらによって導入された概念であるemph{width}の一般化である,問題の難易度を特徴付ける量を導入することにより述べる。
[2014].
関連論文リスト
- Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳（メタデータ） (2024-05-24T04:11:58Z) - Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。
我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。
本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文 参考訳（メタデータ） (2024-02-02T13:31:24Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed
Bandit [65.268245109828]
このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。
CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。
提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
論文 参考訳（メタデータ） (2023-10-24T09:47:32Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Parallelizing Contextual Linear Bandits [82.65675585004448]
並列な)コンテキスト線形バンディットアルゴリズムの族を提示し、その遺残はそれらの完全シーケンシャルなアルゴリズムとほぼ同一である。
また,これらの並列アルゴリズムについて,材料発見や生物配列設計の問題など,いくつかの領域で実証評価を行った。
論文 参考訳（メタデータ） (2021-05-21T22:22:02Z) - Combinatorial Pure Exploration with Bottleneck Reward Function and its
Extension to General Reward Functions [13.982295536546728]
ボトルネック報酬関数 (CPE-B) を用いたコンビネーションピュア探索問題について, 一定の信頼性と固定予算設定の下で検討する。
固定信頼と固定バジェットのアルゴリズムを両立させ,固定信頼設定のサンプル複雑性を低く設定する。
さらに、CPE-Bを一般報酬関数(CPE-G)に拡張し、非自明なサンプル複雑性を持つ一般非線形報酬関数に対する最初の固定信頼アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-24T06:47:51Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。