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

本文研究了一类具有稳态分布的动态随机系统的约束优化问题。在每个状态下，执行一个操作，并根据所选择的操作产生相应的系统成本；目标是在给定服务/需求约束的情况下最小化预期成本。解决这个问题是具有挑战性的，主要困难在于系统的状态分布通常是先验未知的，并且在实践中可能随着时间的推移而变化。处理这一挑战的已知算法，特别是背压算法，存在收敛速度慢、短期性能差的问题。这个项目研究的是在线学习在最优随机系统控制中的价值。初步结果产生了一种称为双重学习的在线学习技术，以及两种相应的在线学习辅助控制策略。拉格朗日乘子是求解约束优化问题的关键量。队列向量发挥了拉格朗日乘子的作用，从而可以利用系统动力学的信息来加速控制算法的学习。基于这一见解，我们系统地研究了在线学习在最优随机系统控制中的价值：1)基本限制：我们研究了所提出的基于在线学习的策略的性能限制，特别是任何控制方案收敛到最优的速度有多快，以及相应的效用-延迟权衡是什么？2)具有部分可观察状态的控制：我们研究在行动的成本函数中具有不确定性的实际场景。我们计划不仅开发高效的算法，而且对所提出的方案进行效用-延迟权衡分析和遗憾分析。3)性能评估：我们评估了所提出算法在不同设置下的性能，并通过跟踪驱动评估来比较它们的优缺点。由于这些随机系统优化问题的通用性和重要性，所提出的方法具有应用于不同领域的潜力，例如显示广告分配、无线网络控制和智能电网。我们利用与工业界的持续合作，在实际应用中传播研究成果。通过这个项目，我们继续努力招募和培训本科生研究人员和代表性不足的群体。

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.