Online Policy Learning and Inference by Matrix Completion

📄 arXiv: 2404.17398v2 📥 PDF

作者: Congyuan Duan, Jingyang Li, Dong Xia

分类: stat.ML, cs.LG

发布日期: 2024-04-26 (更新: 2024-12-19)

💡 一句话要点

提出基于矩阵补全的在线策略学习与推断方法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 在线决策 矩阵补全 策略学习 协同过滤 个性化推荐 交通管理 机器学习

📋 核心要点

  1. 核心问题：在个性化协变量缺失的情况下，现有决策方法难以有效利用集体偏好进行在线决策。
  2. 方法要点：提出了一种结合$ ext{ε}$-贪婪策略与在线梯度下降的两阶段策略学习程序，以解决无协变量决策问题。
  3. 实验或效果：在旧金山停车定价项目中应用该方法，取得了显著的发现，并在性能上超越了基准策略。

📝 摘要（中文）

本研究探讨在个性化协变量缺失的情况下，如何进行在线决策。我们采用协同过滤的方法，基于集体偏好来进行决策。通过假设低维潜在特征，我们将无协变量的决策问题形式化为矩阵补全赌博问题。提出了一种结合$ ext{ε}$-贪婪策略与在线梯度下降算法的策略学习程序，创新的两阶段设计平衡了策略学习的准确性与遗憾性能。针对策略推断，我们开发了一种基于逆倾向加权的在线去偏方法，并建立了其渐近正态性。该方法应用于旧金山停车定价项目的数据，揭示了有趣的发现，并超越了基准策略。

🔬 方法详解

问题定义：本论文旨在解决在缺乏个性化协变量的情况下，如何进行有效的在线决策。现有方法通常依赖于丰富的协变量信息，导致在信息不足时性能下降。

核心思路：我们通过协同过滤的方式，假设存在低维潜在特征，将无协变量的决策问题转化为矩阵补全赌博问题。结合$ ext{ε}$-贪婪策略与在线梯度下降算法，提出了一种新的策略学习程序。

技术框架：整体方法分为两个主要阶段：第一阶段为策略学习，采用$ ext{ε}$-贪婪策略进行决策；第二阶段为参数估计，使用在线梯度下降优化算法。

关键创新：本研究的创新在于提出了两阶段的设计，既考虑了策略学习的准确性，又兼顾了遗憾性能。此外，开发的在线去偏方法基于逆倾向加权，具有渐近正态性。

关键设计：在策略学习中，设置了$ ext{ε}$参数以平衡探索与利用；在在线梯度下降中，采用了适应性学习率以提高收敛速度。

📊 实验亮点

在旧金山停车定价项目中，所提出的方法显著超越了基准策略，具体性能提升幅度未知，展示了在缺乏个性化协变量情况下的有效性与实用性。

🎯 应用场景

该研究的潜在应用领域包括智能交通系统、个性化推荐系统以及其他需要实时决策的场景。通过有效的在线决策方法，可以显著提升资源利用效率和用户体验，未来可能在多个行业产生深远影响。

📄 摘要（原文）

Is it possible to make online decisions when personalized covariates are unavailable? We take a collaborative-filtering approach for decision-making based on collective preferences. By assuming low-dimensional latent features, we formulate the covariate-free decision-making problem as a matrix completion bandit. We propose a policy learning procedure that combines an $\varepsilon$-greedy policy for decision-making with an online gradient descent algorithm for bandit parameter estimation. Our novel two-phase design balances policy learning accuracy and regret performance. For policy inference, we develop an online debiasing method based on inverse propensity weighting and establish its asymptotic normality. Our methods are applied to data from the San Francisco parking pricing project, revealing intriguing discoveries and outperforming the benchmark policy.