論文の概要: Matroid Semi-Bandits in Sublinear Time
- arxiv url: http://arxiv.org/abs/2405.17968v1
- Date: Tue, 28 May 2024 08:55:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-29 19:28:09.176180
- Title: Matroid Semi-Bandits in Sublinear Time
- Title（参考訳）: 準線形時間におけるマトロイドセミバンド
- Authors: Ruo-Chun Tzeng, Naoto Ohsaka, Kaito Ariu,
- Abstract要約: 本研究では,マトロイド半帯域問題について検討し,各ラウンドで学習者が実現可能な集合からK$アームのサブセットを再生する。
我々は,マトロイドの共通クラスに対して,サンプリングルールを$K$でサブリニア化するFasterCUCBを提案する。
- 参考スコア（独自算出の注目度）: 11.98212766542468
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the matroid semi-bandits problem, where at each round the learner plays a subset of $K$ arms from a feasible set, and the goal is to maximize the expected cumulative linear rewards. Existing algorithms have per-round time complexity at least $\Omega(K)$, which becomes expensive when $K$ is large. To address this computational issue, we propose FasterCUCB whose sampling rule takes time sublinear in $K$ for common classes of matroids: $O(D\text{ polylog}(K)\text{ polylog}(T))$ for uniform matroids, partition matroids, and graphical matroids, and $O(D\sqrt{K}\text{ polylog}(T))$ for transversal matroids. Here, $D$ is the maximum number of elements in any feasible subset of arms, and $T$ is the horizon. Our technique is based on dynamic maintenance of an approximate maximum-weight basis over inner-product weights. Although the introduction of an approximate maximum-weight basis presents a challenge in regret analysis, we can still guarantee an upper bound on regret as tight as CUCB in the sense that it matches the gap-dependent lower bound by Kveton et al. (2014a) asymptotically.
- Abstract（参考訳）: 本研究では,各ラウンドにおいて学習者が実現可能な集合からK$アームのサブセットを再生し,期待される累積線形報酬を最大化するマトロイド半帯域問題について検討する。
既存のアルゴリズムは時間単位の複雑さを少なくとも$\Omega(K)$としており、K$が大きければ高価になる。
この計算問題に対処するために、FasterCUCBを提案し、そのサンプリングルールは、マトロイドの共通クラスに対して$K$で時間サブ線形をとる:$O(D\text{ polylog}(K)\text{ polylog}(T))$ for uniform matroids, partition matroids, and graphical matroids, $O(D\sqrt{K}\text{ polylog}(T))$ for transversal matroids。
ここでは、$D$は腕の任意の実現可能な部分集合の最大要素数であり、$T$は地平線である。
本手法は内積重量に対する近似最大重量基底の動的維持に基づく。
近似的最大重み基底の導入は、後悔解析において挑戦となるが、Kveton et al (2014a) の漸近的にギャップ依存的下界と一致するという意味では、CUCB と同じくらい強い後悔の上限を保証できる。
関連論文リスト
- Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
制約のある、必ずしも単調な部分モジュラーでなくても、比が1/e$より大きい全ての既知の近似アルゴリズムは連続的な考えを必要とする。
アルゴリズムでは, 単純なランダム化グレディアルゴリズムを用いて, サイズとマトロイドの制約の双方について最もよく知られた近似比を求める。
論文 参考訳（メタデータ） (2024-05-08T16:39:59Z) - 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) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Deletion Robust Submodular Maximization over Matroids [27.83996903538686]
古典的マトロイド制約の下で, 問題の削除頑健バージョンについて検討する。
定数係数近似アルゴリズムを提案し、その空間複雑性はマトロイドのランク$k$に依存する。
実世界のデータセット上でのアルゴリズムの有効性を示す詳細な実験結果を用いて理論的結果を補完する。
論文 参考訳（メタデータ） (2022-01-31T11:15:56Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。
我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。
鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
論文 参考訳（メタデータ） (2021-01-30T21:51:47Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Approximability of Monotone Submodular Function Maximization under
Cardinality and Matroid Constraints in the Streaming Model [22.637004266371545]
単一パスストリーミングモデルで1-frac1e$を超える濃度とマトロイドの制約に対する近似比の最初の下限を示す。
近似比が $fracK2K-1$ と $frac12$ であるような基数とマトロイドの制約に対する弱いオーラルストリーミングアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-02-13T12:33:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。