パラメトリック選択バンディットにおけるパレート最適性について
arXiv stat.ML / 2026/4/27
💬 オピニオンDeveloper Stack & InfrastructureIdeas & Deep AnalysisModels & Research
要点
- 本論文は、確率的な選好の下でのオンライン・アソートメント最適化を扱い、累積売上の最大化だけでなく、売上差の事後推論の質も同時に重視することを目的としています。
- 強制探索を伴う楽観（OFU）手法を解析し、逐次意思決定用には全観測を用いる正則化最大尤度推定器、推論用には探索ラウンドのみに基づく推定器の2つを組み合わせます。
- 一般理論として、予測可能なスコア代理と、1ラウンドごとの行動依存の曲率支配といった条件の下で、自己正規化濃度不等式、尤度に基づく楕円体信頼集合定理、最適化誤差を明示的に織り込んだ後悔（regret）境界を導出します。
- 多項ロジット（MNL）モデルでは、スコア／曲率の代理を具体的に提示し、バランスの取れた間隔付き単一探索（singleton-exploration）スケジュールにより、後悔がO~(n_T + T/\sqrt{n_T})、売上差の誤差がO~(1/\sqrt{n_T})で達成できることを示し、積（product）レベルで一致する下界も与えます。
- n_T \asymp T^\alpha の多項探索（polynomial exploration）族において、後悔率がO~(T^{max{\alpha,1-\alpha/2}})、推論率がO~(T^{-\alpha/2})となり、\alpha\in[2/3,1) がレート-wise でパレート優越（undominated）な区間であることを明らかにし、後悔指数を最小化する唯一の釣り合い点として \alpha=2/3 を特定します。さらに、Exponomial Choice と Nested Logit でも一般枠組みを具体化しうる十分条件を示しています。
