Exponential weight algorithm in continuous time

• 成果类型: Article; Proceedings Paper
• 署名作者: Sorin, Sylvain
• 署名单位: heSam Universite; Conservatoire National Arts & Metiers (CNAM); Institut Polytechnique de Paris; Ecole Polytechnique; Sorbonne Universite
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0111-y
• 发表日期: 2009
• 页码: 513-528
• 关键词: stochastic approximations; regret

摘要

The exponential weight algorithm has been introduced in the framework of discrete time on-line problems. Given an observed process {X-m}(m)=1,2,... the input at stage m + 1 is an exponential function of the sum S-m = Sigma(m)(l=1) X-l. We define the analog algorithm for a continuous time process X-t and prove similar properties in terms of external or internal consistency. We then deduce results for discrete time from their counterpart in continuous time. Finally we compare this approach to another continuous time approximation of a discrete time exponential algorithm based on the average sum Sm/m.