論文の概要: Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification

• arxiv url: http://arxiv.org/abs/2605.25592v1
• Date: Mon, 25 May 2026 08:41:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-26 19:50:19.5262
• Title: Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification
• Title（参考訳）: 最適配置同定のための多項ロジットモデルの最適設計
• Authors: Joongkyu Lee, Min-hwan Oh,
• Abstract要約: マルチノミアルロジット(MNL)バンドの最適設計について検討した。 線型あるいは一般化された線形帯域とは異なり、MNLバンドは非線形作用空間を持つ。 我々は,MNLの盗賊を識別する最善のアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 39.805192541498634
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We study optimal experimental design for multinomial logit (MNL) bandits, where an agent repeatedly selects a subset of $K$ items from a ground set of size $N$ and observes single-choice feedback. Unlike linear or generalized linear bandits, MNL bandits have a combinatorial action space, which makes classical optimal design approaches and naive optimization over all subsets computationally intractable. We propose a computationally efficient optimal design framework for MNL models that achieves both statistical efficiency and scalability through two complementary approaches: (i) an exact or certified-approximate reformulation of the design oracle as a $0$-$1$ mixed-integer linear program (MILP) with solver-certified early stopping, and (ii) a fully polynomial-time lifted design that replaces the nonlinear objective with a tractable surrogate. Using the Kiefer-Wolfowitz equivalence theorem, we establish near G-optimality guarantees and characterize the induced statistical-computational trade-offs. As an application, we develop a best assortment identification algorithm for MNL bandits with linear utilities and non-uniform revenues, and prove an instance-dependent sample complexity of $\tilde{O}\big(\frac{d \log N}{Δ^2}\big)$, where $d$ is the feature dimension, $N$ is the number of arms, and $Δ$ is the minimum revenue gap.
• Abstract（参考訳）: マルチノードロジット(MNL)バンドイットの最適実験設計について検討し, エージェントがN$の基底集合からK$アイテムのサブセットを繰り返し選択し, 単一選択フィードバックを観測する。 線形あるいは一般化された線形バンドイットとは異なり、MNLバンドイットは組合せ的作用空間を持ち、古典的最適設計アプローチと全ての部分集合を計算的に難解に最適化する。 統計的効率とスケーラビリティを両立させるMNLモデルのための計算効率の良い最適設計フレームワークを提案する。 i) 設計書の正当又は正当性を0$-1$混合整数線形プログラム(MILP)として、解決者認定早期停止による改定 (ii) 非線形目的をトラクタブル・サロゲートに置き換える完全多項式時昇降設計。 キーファー=ヴォルフォヴィッツ同値定理を用いて、G-最適性保証をほぼ確立し、誘導された統計計算トレードオフを特徴づける。 アプリケーションとして、線形ユーティリティと非一様収益を持つMNLバンディットの最良の分類識別アルゴリズムを開発し、インスタンス依存のサンプル複雑性を$\tilde{O}\big(\frac{d \log N}{Δ^2}\big)$で証明する。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem [12.04919729571293]
  本稿では、旅行セールスマン問題(TSP)に対するテンソルネットワークジェネレータ強化最適化(TN-GEO)フレームワークの適用について述べる。 提案手法では,自動微分可能な行列積状態(MPS)を生成モデルとして,テンソルネットワークのBornマシンを用いる。 局所的な相関に注目する$k$-site variantsは、フルMPSの場合よりもよい結果を示す。
  論文  参考訳（メタデータ） (2026-02-12T21:18:19Z)
• Scalable Neural Incentive Design with Parameterized Mean-Field Approximation [28.20524168049273]
  力学と報酬がリプシッツであるとき、有限$N$ ID の目標は、PMFG によって $mathscrO(frac1sqrtN)$ で近似されることを示す。 さらに、反復平衡作用素の明示的な微分を利用して勾配を効率的に計算する、随伴平均集中設計(AMID)アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-10-24T13:18:54Z)
• Best-of-$\infty$ -- Asymptotic Performance of Test-Time Compute [10.167365483866663]
  我々は,大言語モデル (LLMs) において,多数決に基づく最安の$N$について検討する。 回答合意に基づいてN$を選択する適応生成方式を提案する。 フレームワークを複数のLLMの重み付けアンサンブルに拡張し、そのような混合物が個々のモデルより優れていることを示す。
  論文  参考訳（メタデータ） (2025-09-25T12:41:05Z)
• Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits [8.013444110633223]
  自動機構設計のための線形プログラム(LP)に最適解のクラスを解析的に導出する。 これらの解は、元の定式化における変数の総数よりも指数関数的に小さい基本変数の集合を用いて表すことができる。 本稿では,この用語の評価をマルチアーム・バンディット(MAB)問題に翻訳することでこの問題に対処する。
  論文  参考訳（メタデータ） (2024-11-30T03:59:36Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)

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

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