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