論文の概要: Sum-max Submodular Bandits
- arxiv url: http://arxiv.org/abs/2311.05975v1
- Date: Fri, 10 Nov 2023 10:18:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-13 15:15:43.008723
- Title: Sum-max Submodular Bandits
- Title（参考訳）: Sum-max サブモジュラバンド
- Authors: Stephen Pasteris, Alberto Rumi, Fabio Vitale, Nicol\`o Cesa-Bianchi
- Abstract要約: このクラスのすべての関数が擬凸と呼ばれる重要な性質を満たすことを示す。
この境界は、単純で効率的なアルゴリズムによって達成され、帯域幅のフィードバックを持つオンラインモノトン部分モジュラーに対して$widetildeObig(T2/3big)$ regret boundで大幅に改善される。
- 参考スコア（独自算出の注目度）: 7.337919355153117
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many online decision-making problems correspond to maximizing a sequence of
submodular functions. In this work, we introduce sum-max functions, a subclass
of monotone submodular functions capturing several interesting problems,
including best-of-$K$-bandits, combinatorial bandits, and the bandit versions
on facility location, $M$-medians, and hitting sets. We show that all functions
in this class satisfy a key property that we call pseudo-concavity. This allows
us to prove $\big(1 - \frac{1}{e}\big)$-regret bounds for bandit feedback in
the nonstochastic setting of the order of $\sqrt{MKT}$ (ignoring log factors),
where $T$ is the time horizon and $M$ is a cardinality constraint. This bound,
attained by a simple and efficient algorithm, significantly improves on the
$\widetilde{O}\big(T^{2/3}\big)$ regret bound for online monotone submodular
maximization with bandit feedback.
- Abstract（参考訳）: 多くのオンライン意思決定問題は、部分モジュラ函数の列の最大化に対応する。
本研究では,sum-max関数(sum-max function)を導入する。sum-max関数は,$k$-bandits, combinatorial bandits,および施設ロケーションにおけるbanditバージョン,$m$-medians,およびhitsetなど,いくつかの興味深い問題をキャプチャするモノトーンサブモジュラー関数のサブクラスである。
このクラス内のすべての関数は、疑似コンビニティと呼ばれる重要な特性を満たす。
これにより、$t$が時間軸であり、$m$が濃度制約であるような、$\sqrt{mkt}$(ログ因子を無視する)の順序の非確率的な設定において、バンドイットフィードバックのための$\big(1 - \frac{1}{e}\big)$-regret境界を証明できる。
この境界は、単純で効率的なアルゴリズムによって達成され、ブレイジットフィードバックによるオンラインモノトン部分モジュラー最大化に対する$\widetilde{O}\big(T^{2/3}\big)$ regret boundで大幅に改善される。
関連論文リスト
- Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - Minimax Optimal Submodular Optimization with Bandit Feedback [13.805872311596739]
単調な部分モジュラー集合関数 $f: 2[n] rightarrow [0,1]$ をバンドイットフィードバックの下で最大化する。
具体的には、$f$は学習者には知られていないが、各時点で$t=1,dots,T$は、$|S_t| leq k$でセットの$S_tサブセット[n]$を選択し、$eta_t$が平均ゼロのサブガウスノイズである場合に、$f(S_t) + eta_t$を受け取る。
論文 参考訳（メタデータ） (2023-10-27T20:19:03Z) - Bandit Multi-linear DR-Submodular Maximization and Its Applications on
Adversarial Submodular Bandits [21.54858035450694]
分割マトロイド制約を持つ部分モジュラー帯域に対するサブ線形後悔アルゴリズムを提案する。
バンドイットの逐次部分モジュラーに対して、既存の研究はO(T2/3)$ regret を証明し、近似比は1/2$である。
論文 参考訳（メタデータ） (2023-05-21T08:51:55Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - 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) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Improved Regret Bounds for Online Submodular Maximization [10.089520556398575]
我々は、各ステップ$tin[T]$において、固定凸からアクション$x_t$を選択し、コンパクトなドメインセット$mathcalK$を選択するオンライン最適化問題を考える。
ユーティリティ関数 $f_t(cdot)$ が明らかになり、アルゴリズムはペイオフ $f_t(x_t)$ を受け取る。
論文 参考訳（メタデータ） (2021-06-15T02:05:35Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。