We study the problem of Online Convex Optimization (OCO) with memory, which allows loss functions to depend on past decisions and thus captures temporal effects of learning problems. In this paper, we introduce dynamic policy regret as the performance measure to design algorithms robust to non-stationary environments, which competes algorithms' decisions with a sequence of changing comparators. We propose a novel algorithm for OCO with memory that provably enjoys an optimal dynamic policy regret. The key technical challenge is how to control the switching cost, the cumulative movements of player's decisions, which is neatly addressed by a novel decomposition of dynamic policy regret and an appropriate meta-expert structure. Furthermore, we generalize the results to the problem of online non-stochastic control, i.e., controlling a linear dynamical system with adversarial disturbance and convex loss functions. We derive a novel gradient-based controller with dynamic policy regret guarantees, which is the first controller competitive to a sequence of changing policies.


翻译:我们用记忆来研究在线 convex 优化(OCO)的问题,让损失功能依赖过去的决定,从而捕捉学习问题的时间影响。在本文中,我们引入了动态政策遗憾作为性能衡量标准,以设计对非静止环境强健的算法,这种算法与一系列变化的参照方相竞争。我们为OCO提出了一个具有记忆的新式算法,这种算法可以令人理解地享有最佳的动态政策悔恨。关键的技术挑战是如何控制转换成本、玩家决定的累积移动,这种变化通过动态政策悔恨和适当的元专家结构的新颖的分解得到了很好的解决。此外,我们把结果概括化为在线非静态控制的问题,即控制线性动态系统,带有对抗性扰动和convex损失功能。我们产生了一个新的具有动态政策悔恨保证的梯度控制器,这是第一个对改变政策的顺序具有竞争力的控制器。

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
已删除
将门创投
3+阅读 · 2019年6月12日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
A Modern Introduction to Online Learning
Arxiv
20+阅读 · 2019年12月31日
Arxiv
3+阅读 · 2018年10月5日
Hierarchical Deep Multiagent Reinforcement Learning
Arxiv
8+阅读 · 2018年9月25日
Arxiv
3+阅读 · 2018年1月31日
VIP会员
相关VIP内容
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
已删除
将门创投
3+阅读 · 2019年6月12日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员