CIF: Small: The Power of Online Learning in Stochastic System Optimization

CIF：小：随机系统优化中在线学习的力量

• 批准号: 1423542
• 负责人: Xin Liu
• 金额: $ 37.66万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-10-01 至 2018-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423542&HistoricalAwards=false
• 关键词: CIF; Small; Power; Online; Learning

This project considers a constrained optimization problem applied to a stochastic system with dynamic system states that have a stationary state distribution. At each state, an operation is implemented and a corresponding system cost occurs depending on the chosen action; the objective is to minimize the expected cost given service/demand constraints. Solving this problem is challenging and the main difficulty comes from the fact that the state distribution of the system is often unknown a priori and may change over time in practice. Known algorithms that handle this challenge, in particular, Backpressure algorithms, suffer from a slow convergence speed and poor short-term performance. This project instead investigates the value of online learning in optimal stochastic system control. Preliminary results have produced an online-learning technique called dual learning, along with two corresponding online-learning-aided control strategies. Lagrange multipliers form key quantities in solving a constrained optimization problem; the queue vector turns out to play the role of Lagrange multiplier, and thus one can utilize the information of the system dynamics for accelerating the learning of the control algorithm. Based on this insight, we systematically study the value of online learning in optimal stochastic system control in the following thrusts: 1) Fundamental Limits: We investigate the performance limits of the proposed online-learning-based-strategies, in particular, how fast is it possible for any control scheme to converge to the optimal and what is the corresponding utility-delay tradeoff? 2) Control with partially observable states: We study the practical scenario where one has uncertainty in the cost function of an action. We plan to not only develop efficient algorithms, but also conduct utility-delay tradeoff analysis and regret analysis for the proposed schemes. 3) Performance Evaluation: We evaluate the performance of the proposed algorithms under various settings and through trace-driven evaluations to compare their pros and cons. Because the generality and importance of such stochastic system optimization problems, the proposed approaches have the potential to be applied in different areas, such as display-advertisement allocation, wireless network control, and Smart Grids. We leverage on-going collaborations with industry to disseminate the research results in real applications. We continue the effort in recruiting and training undergraduate researchers and under-represented groups through this project.

该项目认为具有具有固定状态分布的动态系统状态的随机系统的受限优化问题。在每个状态下，都会实施操作，并根据所选的操作发生相应的系统成本；目的是最大程度地减少给定服务/需求限制的预期成本。解决这个问题是具有挑战性的，主要的困难源于以下事实：系统的状态分布通常是未知的，并且在实践中可能会随着时间的推移而变化。应对这一挑战的已知算法，尤其是背压算法，其收敛速度缓慢且短期性能较差。相反，该项目研究了在线学习在最佳随机系统控制中的价值。初步结果已经产生了一种称为双重学习的在线学习技术，以及两种相应的在线学习辅助控制策略。拉格朗日乘数在解决约束优化问题时形成关键数量；队列矢量事实证明起着拉格朗日乘数的作用，因此可以利用系统动力学的信息来加速控制算法的学习。基于这种见识，我们系统地研究了以下方向的最佳随机系统控制中在线学习的价值：1）基本限制：我们研究了拟议的基于在线学习的基于网络的策略的性能限制，尤其是任何控制方案都可以融合到最佳和什么是最佳和什么是相应的公用事业票房票房？ 2）以部分可观察的状态进行控制：我们研究了一个行动成本函数不确定性的实际情况。我们不仅计划开发有效的算法，而且还计划对拟议方案进行公用事业 - 否决分析和遗憾分析。 3）绩效评估：我们在各种环境下以及通过跟踪驱动的评估来评估拟议算法的性能，以比较其利弊。 由于此类随机系统优化问题的一般性和重要性，因此所提出的方法有可能在不同领域（例如展示广告分配，无线网络控制和智能电网）应用。我们利用与行业进行的持续合作来传播实际应用中的研究结果。我们继续努力通过该项目招募和培训本科研究人员和代表性不足的群体。

项目成果

Adaptive Exploration-Exploitation Tradeoff for Opportunistic Bandits

• 发表时间: 2017-09
• 作者: Huasen Wu;Xueying Guo;Xin Liu

Cellular Network Configuration via Online Learning and Joint Optimization

通过在线学习和联合优化进行蜂窝网络配置

• 发表时间: 2017
• 期刊: IEEE Big Data Conference
• 作者: Guo, Xueying;Trimponiasy, George;Wang, Xiaoxiao;Chen, Zhitang;Geng, Yanhui;Liu, Xin
• 通讯作者: Liu, Xin