論文の概要: Adversarial Combinatorial Bandits with General Non-linear Reward Functions

• arxiv url: http://arxiv.org/abs/2101.01301v1
• Date: Tue, 5 Jan 2021 00:56:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-11 21:45:52.274809
• Title: Adversarial Combinatorial Bandits with General Non-linear Reward Functions
• Title（参考訳）: 一般非線形リワード機能を有する対数組合せ帯域
• Authors: Xi Chen and Yanjun Han and Yining Wang
• Abstract要約: 既知の非線形報酬関数を用いて対向性バンディットを研究し、対向性線形バンディットに関する既存の研究を延長する。 我々は、$N$の腕と$K$の腕のサブセットが$T$の期間のそれぞれで選択されている場合、ミニマックスの最適な後悔は$widetildeTheta_d(Nd T)$報酬関数が$dK$の$d$度であり、$ta_K(sqrtK T)$報酬関数が低度ではない場合です。
• 参考スコア（独自算出の注目度）: 29.775097827244853
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we study the adversarial combinatorial bandit with a known non-linear reward function, extending existing work on adversarial linear combinatorial bandit. {The adversarial combinatorial bandit with general non-linear reward is an important open problem in bandit literature, and it is still unclear whether there is a significant gap from the case of linear reward, stochastic bandit, or semi-bandit feedback.} We show that, with $N$ arms and subsets of $K$ arms being chosen at each of $T$ time periods, the minimax optimal regret is $\widetilde\Theta_{d}(\sqrt{N^d T})$ if the reward function is a $d$-degree polynomial with $d< K$, and $\Theta_K(\sqrt{N^K T})$ if the reward function is not a low-degree polynomial. {Both bounds are significantly different from the bound $O(\sqrt{\mathrm{poly}(N,K)T})$ for the linear case, which suggests that there is a fundamental gap between the linear and non-linear reward structures.} Our result also finds applications to adversarial assortment optimization problem in online recommendation. We show that in the worst-case of adversarial assortment problem, the optimal algorithm must treat each individual $\binom{N}{K}$ assortment as independent.
• Abstract（参考訳）: 本稿では,非線形報酬関数を持つ逆組合せバンディットについて検討し,逆線形組合せバンディットに関する既存の研究を拡張した。 一般の非線形報酬を伴う相反的組合せ的バンディットは、バンディット文学において重要なオープン問題であり、線形報酬、確率的バンディット、半バンディットフィードバックの場合には大きなギャップがあるかどうかはまだ不明である。 例えば、$N$のアームと$K$のアームのサブセットが$T$のタイムに選択されている場合、ミニマックス最適後悔は$\widetilde\Theta_{d}(\sqrt{N^d T})$ もし報酬関数が$d$次多項式で$d<K$と$\Theta_K(\sqrt{N^K T})$ならば、報酬関数は低次多項式ではない。 {Both bounds is significantly different from the bound $O(\sqrt{\mathrm{poly}(N,K)T})$ for the linear case, which suggests that is a fundamental gap between the linear and non-linear reward structure。 また,オンラインレコメンデーションにおける逆ソート最適化問題に対する応用も見いだした。 逆数分解問題の最悪の場合、最適なアルゴリズムは個々の$\binom{N}{K}$アソートを独立に扱う必要がある。

関連論文リスト

• Nash Regret Guarantees for Linear Bandits [12.494184403263338]
  我々は,Nashが$Oleft(sqrtfracdnuT log(T |X|)right)$を後悔するアルゴリズムを開発した。 さらに、アームの集合 X$ が必ずしも有限ではない線形バンドイットのインスタンスに対処すると、ナッシュ後悔の上限 $Oleft( fracdfrac54nufrac12sqrtT log(T)right)$ が得られる。
  論文  参考訳（メタデータ） (2023-10-03T12:58:10Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• 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)
• 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)
• DART: aDaptive Accept RejecT for non-linear top-K subset identification [34.68931784199599]
  我々は、各ステップでN$アームからK$を選択するという盗賊問題を考える。 本稿では,各アームのフィードバックや報酬関数の線形性を必要としない新しいアルゴリズムを提案する。 我々のアルゴリズムであるaDaptive Accept RejecT (DART)は、良好な腕を逐次見つけ、信頼境界に基づいて悪い腕を除去する。
  論文  参考訳（メタデータ） (2020-11-16T02:10:06Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
  低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。 低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-04T15:30:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。