平衡收益与推断精度,提出新型在线商品组合优化方法。
On Pareto Optimality for Parametric Choice Bandits
- 采用探索性乐观策略,分离决策与推断数据提升可靠性
- 在MNL模型下实现近似最优的后悔率与对比误差控制
- 适用于需兼顾收益和统计推断的推荐系统场景
研究在随机选择下同时关注累计收益和事后收益对比推断质量的在线商品组合优化问题。提出一种强制探索的乐观策略,结合两种正则化最大似然估计器:一个基于全部观测用于序列决策,另一个仅基于探索阶段数据用于推断。在可预测评分代理和每轮动作相关的曲率支配条件下,建立自归一化浓度不等式、基于似然的椭球置信集定理及包含优化误差的近似乐观动作后悔界。针对多项式对数(MNL)模型,导出显式的评分与曲率代理,证明均衡间隔单件探索调度可实现坐标覆盖,从而获得后悔率 $ ilde{oldsymbol{O}}(n_T + T/ extstyle ootrom{2} m{n_T})$ 与收益对比误差 $ ilde{oldsymbol{O}}(1/ extstyle ootrom{2} m{n_T})$(含固定问题相关因子)。硬两商品子类在产品层面给出匹配下界。因此,在多项式探索族 $n_T owtie T^α$ 内,后悔率与推断率分别为 $ ilde{oldsymbol{O}}(T^{ extstyleoldsymbol{ ext{max}igrace{α,1−α/2igrace}}})$ 和 $ ilde{oldsymbol{O}}(T^{-α/2})$;故 $α∈[2/3,1)$ 为率意义下不可被支配区间,且 $α=2/3$ 是最小化后悔指数的唯一平衡点。最后,对指数选择与嵌套对数模型给出可验证的充分条件以实例化通用框架。
原文摘要 · Abstract (English)
We study online assortment optimization under stochastic choice when a decision maker simultaneously values cumulative revenue performance and the quality of post-hoc inference on revenue contrasts. We analyze a forced-exploration optimism-in-the-face-of-uncertainty (OFU) scheme that combines two regularized maximum-likelihood estimators: one based on all observations for sequential decision making, and one based only on exploration rounds for inference. Our general theory is developed under predictable score proxies and per-round action-dependent curvature domination. Under these conditions we establish a self-normalized concentration inequality, a likelihood-based ellipsoidal confidence-set theorem, and a regret bound for approximate optimistic actions that explicitly accounts for optimization error. For the multinomial logit (MNL) model we derive explicit score and curvature proxies and show that a balanced spaced singleton-exploration schedule yields realized coordinate coverage, implying regret $\Otilde(n_T + T/\sqrt{n_T})$ and revenue-contrast error $\Otilde(1/\sqrt{n_T})$ up to fixed problem-dependent factors. A hard two-assortment subclass yields a matching lower bound at the product level. Consequently, within the polynomial exploration family $n_T \asymp T^α$, the regret and inference rates become $\Otilde(T^{\max\{α,1-α/2\}})$ and $\Otilde(T^{-α/2})$, respectively; hence $α\in[2/3,1)$ is the rate-wise Pareto-undominated interval and $α=2/3$ is the unique balancing point that minimizes the regret exponent. Finally, for the Exponomial Choice and Nested Logit models we state verifiable sufficient conditions that would instantiate the general framework.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。