论文标题
使用非易变的指数总和从匪徒反馈中进行动态结构估计
Dynamic Structure Estimation from Bandit Feedback using Nonvanishing Exponential Sums
论文作者
论文摘要
这项工作解决了欧几里得空间中定期表演的离散动态系统的动态结构估计问题。我们假设观察结果以一种被高斯噪声污染的匪徒反馈形式依次获得。在如此一般的关于噪声分布的假设下，我们仔细地确定了一组周期结构的可回收信息。我们的主要结果是（计算和样本）有效算法，这些算法利用了指数总和的渐近行为，以有效地平均消除噪声效应，同时阻止信息从消失中估计。特别是，新型Weyl和指数总和的变体的新颖使用使我们能够为线性系统提取频谱信息。我们为我们的算法提供样品复杂性界限，并在包括细胞自动机在内的玩具示例的模拟中实验验证了我们的理论主张。
This work tackles the dynamic structure estimation problems for periodically behaved discrete dynamical system in the Euclidean space. We assume the observations become sequentially available in a form of bandit feedback contaminated by a sub-Gaussian noise. Under such fairly general assumptions on the noise distribution, we carefully identify a set of recoverable information of periodic structures. Our main results are the (computation and sample) efficient algorithms that exploit asymptotic behaviors of exponential sums to effectively average out the noise effect while preventing the information to be estimated from vanishing. In particular, the novel use of the Weyl sum, a variant of exponential sums, allows us to extract spectrum information for linear systems. We provide sample complexity bounds for our algorithms, and we experimentally validate our theoretical claims on simulations of toy examples, including Cellular Automata.
