論文の概要: Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2506.13163v1
• Date: Mon, 16 Jun 2025 07:19:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:47.682914
• Title: Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback
• Title（参考訳）: 帯域フィードバックをもつロジスティック文脈スレート帯域の効率的なアルゴリズム
• Authors: Tanmay Goyal, Gaurav Sinha,
• Abstract要約: 本稿では,ロジスティック・コンテクスト・スレート・バンド問題について考察する。 選択したスレートに対して、ロジスティックモデルにより決定された単一のバイナリ報酬が観測される。 本稿では,Slate-GLM-OFUとSlate-GLM-TSの2つのアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.8287206589886881
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the Logistic Contextual Slate Bandit problem, where, at each round, an agent selects a slate of $N$ items from an exponentially large set (of size $2^{\Omega(N)}$) of candidate slates provided by the environment. A single binary reward, determined by a logistic model, is observed for the chosen slate. Our objective is to develop algorithms that maximize cumulative reward over $T$ rounds while maintaining low per-round computational costs. We propose two algorithms, Slate-GLM-OFU and Slate-GLM-TS, that accomplish this goal. These algorithms achieve $N^{O(1)}$ per-round time complexity via local planning (independent slot selections), and low regret through global learning (joint parameter estimation). We provide theoretical and empirical evidence supporting these claims. Under a well-studied diversity assumption, we prove that Slate-GLM-OFU incurs only $\tilde{O}(\sqrt{T})$ regret. Extensive experiments across a wide range of synthetic settings demonstrate that our algorithms consistently outperform state-of-the-art baselines, achieving both the lowest regret and the fastest runtime. Furthermore, we apply our algorithm to select in-context examples in prompts of Language Models for solving binary classification tasks such as sentiment analysis. Our approach achieves competitive test accuracy, making it a viable alternative in practical scenarios.
• Abstract（参考訳）: 筆者らはロジスティック・コンテクスト・スレート・バンドイット(Logistic Contextual Slate Bandit)問題について検討し、各ラウンドにおいて、エージェントは、環境によって提供される候補スレートの指数的に大きな集合(サイズ2^{\Omega(N)}$)から、N$アイテムのスレートを選択する。 選択したスレートに対して、ロジスティックモデルにより決定された単一のバイナリ報酬が観測される。 本研究の目的は,ラウンド当たりの計算コストを低く抑えつつ,T$ラウンドに対する累積報酬を最大化するアルゴリズムを開発することである。 本稿では,Slate-GLM-OFUとSlate-GLM-TSの2つのアルゴリズムを提案する。 これらのアルゴリズムは、局所的な計画(独立スロット選択)と、グローバルラーニング(ジョイントパラメータ推定)による低後悔(英語版)により、全時間あたりの複雑さを$N^{O(1)}$に達成する。 これらの主張を支持する理論的および実証的な証拠を提供する。 十分に研究された多様性の仮定の下で、Slate-GLM-OFU は $\tilde{O}(\sqrt{T})$ regret しか生じないことを証明する。 広範囲にわたる総合的な実験により、我々のアルゴリズムは最先端のベースラインを一貫して上回り、最小の後悔と最速のランタイムを達成している。 さらに、感情分析などの二項分類タスクを解くために、言語モデルのプロンプトにおける文脈内例を選択するために、本アルゴリズムを適用した。 提案手法は競争力のあるテスト精度を達成し,現実的なシナリオで実現可能な代替手段となる。

関連論文リスト

• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Improved Active Multi-Task Representation Learning via Lasso [44.607652031235716]
  本稿では,L1-regularized-relevance-based(nu1$)戦略の優位性を示す。 また、サンプルコストに敏感な設定で$nu1$ベースの戦略の可能性を特徴付けます。
  論文  参考訳（メタデータ） (2023-06-05T03:08:29Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。 アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。 サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
  論文  参考訳（メタデータ） (2022-11-28T08:40:12Z)
• A Spectral Approach to Item Response Theory [6.5268245109828005]
  本稿では,Raschモデルに対する新しい項目推定アルゴリズムを提案する。 我々のアルゴリズムの中核は、アイテム-イムグラフ上で定義されたマルコフ連鎖の定常分布の計算である。 合成および実生活データセットの実験により、我々のアルゴリズムは、文献でよく使われている手法とスケーラブルで正確で競合することを示した。
  論文  参考訳（メタデータ） (2022-10-09T18:57:08Z)
• Robust Methods for High-Dimensional Linear Learning [0.0]
  統計的に頑健で計算効率の良い線形学習法を高次元バッチ設定で提案する。 バニラスパース、グループスパース、低ランク行列回復など、いくつかのアプリケーションでフレームワークをインスタンス化する。 バニラ $s$-sparsity の場合、重いテールと $eta$-corruption の下で $slog (d)/n$ レートに達することができます。
  論文  参考訳（メタデータ） (2022-08-10T17:00:41Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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