# Dynamic Structure Estimation from Bandit Feedback using Nonvanishing Exponential Sums

arXiv: https://arxiv.org/abs/2206.00861 · HTML: https://mlsanity.com/paper/2206.00861/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 87 references that are in the map.
- First posted on arXiv 2 Jun 2022.

## Builds on (most cited first, 30 of 31)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Stochastic Latent Actor-Critic: Deep Reinforcement Learning with a Latent Variable Model](https://mlsanity.com/paper/1907.00953/) (2019)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning](https://mlsanity.com/paper/2006.08684/) (2020)
- [Active Learning for Nonlinear System Identification with Guarantees](https://mlsanity.com/paper/2006.10277/) (2020)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019)
- [Discovering Governing Equations from Partial Measurements with Deep Delay Autoencoders](https://mlsanity.com/paper/2201.05136/) (2022)
- [Hedging the Drift: Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1903.01461/) (2019)
- [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020)
- [Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes](https://mlsanity.com/paper/2110.15332/) (2021)
- [Spectral Filtering for General Linear Dynamical Systems](https://mlsanity.com/paper/1802.03981/) (2018)
- [Learning Contextual Bandits in a Non-stationary Environment](https://mlsanity.com/paper/1805.09365/) (2018)
- [Learning the Linear Quadratic Regulator from Nonlinear Observations](https://mlsanity.com/paper/2010.03799/) (2020)
- [Learning Latent Dynamics for Partially-Observed Chaotic Systems](https://mlsanity.com/paper/1907.02452/) (2019)
- [Gaussian processes meet NeuralODEs: A Bayesian framework for learning the dynamics of partially observed systems from scarce and noisy data](https://mlsanity.com/paper/2103.03385/) (2021)
- [Sample Complexity of Kalman Filtering for Unknown Systems](https://mlsanity.com/paper/1912.12309/) (2019)
- [Improved rates for prediction and identification of partially observed linear dynamical systems](https://mlsanity.com/paper/2011.10006/) (2020)
- [Operator inference of non-Markovian terms for learning reduced models from partially observed state trajectories](https://mlsanity.com/paper/2103.01362/) (2021)
- [Koopman Spectrum Nonlinear Regulators and Efficient Online Learning](https://mlsanity.com/paper/2106.15775/) (2021)
- [Lyceum: An efficient and scalable ecosystem for robot learning](https://mlsanity.com/paper/2001.07343/) (2020)
- [Scalable Identification of Partially Observed Systems with Certainty-Equivalent EM](https://mlsanity.com/paper/2006.11615/) (2020)
- [Periodic Bandits and Wireless Network Selection](https://mlsanity.com/paper/1904.12355/) (2019)
- [Robust guarantees for learning an autoregressive filter](https://mlsanity.com/paper/1905.09897/) (2019)

## Abstract (arXiv)

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.