論文の概要: Combinatorial Neural Bandits
- arxiv url: http://arxiv.org/abs/2306.00242v1
- Date: Wed, 31 May 2023 23:27:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 19:01:20.515471
- Title: Combinatorial Neural Bandits
- Title（参考訳）: 組合せ神経バンディット
- Authors: Taehyun Hwang, Kyuwook Chai, Min-hwan Oh
- Abstract要約: 学習エージェントが各ラウンドでアームのサブセットを選択し、そのスコアに応じて選択したアームのフィードバックを受け取るというコンテキスト的盗聴問題を考える。
アルゴリズムを提案する: Combinatorial Neural UCB(textttCN-UCB)と Combinatorial Thompson Sampling(textttCN-TS$)。
- 参考スコア（独自算出の注目度）: 10.463365653675694
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We consider a contextual combinatorial bandit problem where in each round a
learning agent selects a subset of arms and receives feedback on the selected
arms according to their scores. The score of an arm is an unknown function of
the arm's feature. Approximating this unknown score function with deep neural
networks, we propose algorithms: Combinatorial Neural UCB ($\texttt{CN-UCB}$)
and Combinatorial Neural Thompson Sampling ($\texttt{CN-TS}$). We prove that
$\texttt{CN-UCB}$ achieves $\tilde{\mathcal{O}}(\tilde{d} \sqrt{T})$ or
$\tilde{\mathcal{O}}(\sqrt{\tilde{d} T K})$ regret, where $\tilde{d}$ is the
effective dimension of a neural tangent kernel matrix, $K$ is the size of a
subset of arms, and $T$ is the time horizon. For $\texttt{CN-TS}$, we adapt an
optimistic sampling technique to ensure the optimism of the sampled
combinatorial action, achieving a worst-case (frequentist) regret of
$\tilde{\mathcal{O}}(\tilde{d} \sqrt{TK})$. To the best of our knowledge, these
are the first combinatorial neural bandit algorithms with regret performance
guarantees. In particular, $\texttt{CN-TS}$ is the first Thompson sampling
algorithm with the worst-case regret guarantees for the general contextual
combinatorial bandit problem. The numerical experiments demonstrate the
superior performances of our proposed algorithms.
- Abstract（参考訳）: 各ラウンドにおいて学習エージェントがアームのサブセットを選択し、そのスコアに応じて選択されたアームに対するフィードバックを受け取る、文脈的組合せバンディット問題を考える。
腕のスコアは、腕の特徴の未知の機能である。
この未知のスコア関数をディープニューラルネットワークで近似するアルゴリズムを提案する: Combinatorial Neural UCB ($\texttt{CN-UCB}$)と Combinatorial Neural Thompson Sampling ($\texttt{CN-TS}$)。
我々は、$\textt{cn-ucb}$が$\tilde{\mathcal{o}}(\tilde{d} \sqrt{t})$または$\tilde{\mathcal{o}}(\sqrt{\tilde{d} t k})$ regret であることを証明する。
$\texttt{CN-TS}$に対して、楽観的なサンプリング手法を適用して、サンプリングされた組合せアクションの楽観性を保証し、$\tilde{\mathcal{O}}(\tilde{d} \sqrt{TK})$の最悪の(頻繁な)後悔を達成する。
私たちの知る限りでは、これらは後悔のパフォーマンス保証を備えた最初の組合せ型ニューラルネットワークバンディットアルゴリズムです。
特に、$\texttt{CN-TS}$は、一般的なコンテクスト組合せバンディット問題に対する最悪の後悔の保証を持つ最初のトンプソンサンプリングアルゴリズムである。
数値実験により,提案するアルゴリズムの優れた性能を示す。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Non-stationary Bandits and Meta-Learning with a Small Set of Optimal
Arms [30.024167992890916]
そこで本研究では,学習者が200ドル(約1万2000円)の帯域幅のタスクに直面する決定について検討する。
敵は各タスクの最適なアームを、M$アームのより小さな(しかし未知の)サブセットで選択することを制約される。
境界は既知のもの(非定常的メタラーニング設定)、あるいは未知のもの(非定常的バンディット設定)である。
論文 参考訳（メタデータ） (2022-02-25T22:28:01Z) - Learning Contextual Bandits Through Perturbed Rewards [107.6210145983805]
標準正規性条件下では、$tildeO(tildedsqrtT)$ regret上界が達成可能であることを示す。
明示的な探索の必要性を排除するために、ニューラルネットワークを更新する際の報酬を混乱させます。
論文 参考訳（メタデータ） (2022-01-24T19:10:22Z) - Neural Contextual Bandits without Regret [47.73483756447701]
ニューラルネットワークを用いて未知の報酬関数を近似する文脈的帯域幅のアルゴリズムを提案する。
我々のアプローチは、$tildemathcalO(T-1/2d)$ rateで最適ポリシーに収束し、$d$は文脈の次元であることを示す。
論文 参考訳（メタデータ） (2021-07-07T11:11:34Z) - Sleeping Combinatorial Bandits [15.004764451770441]
睡眠帯域設定においてよく知られたCUCBアルゴリズムを適用し,それをCSUCBと呼ぶ。
穏やかな条件下では、CSUCBアルゴリズムが$O(sqrtT log (T)$ instance-dependent regret guaranteeを達成することを証明します。
我々の結果は極めて一般的なものであり、非付加的な報酬関数、揮発性アームの可用性、引くべきベースアームの変動数など、実用的な応用によって生じる一般的な環境下で維持されます。
論文 参考訳（メタデータ） (2021-06-03T06:49:44Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - 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) - Neural Thompson Sampling [94.82847209157494]
本稿では,ニューラルトンプソンサンプリング(Neural Thompson Smpling)と呼ばれる新しいアルゴリズムを提案する。
我々のアルゴリズムの中核は報酬の新たな後部分布であり、その平均はニューラルネットワーク近似器であり、その分散は対応するニューラルネットワークのニューラル・タンジェントな特徴に基づいて構築されている。
論文 参考訳（メタデータ） (2020-10-02T07:44:09Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。