mlsanityData to 14 Oct 2026

Dynamic Structure Estimation from Bandit Feedback using Nonvanishing Exponential Sums

arXiv 2206.00861 ↗First posted 2 Jun 2022cs.DM cs.LGcited by 0

Not on the map. Why?

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.

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

31 of 87 references.

References · 31

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  3. 2019Stochastic Latent Actor-Critic: Deep Reinforcement Learning with a Latent Variable Modelcited by 231
  4. 2020Naive Exploration is Optimal for Online LQRcited by 116
  5. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 90
  6. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 86
  7. 2020Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planningcited by 86
  8. 2020Active Learning for Nonlinear System Identification with Guaranteescited by 80
  9. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  10. 2020Approximate information state for approximate planning and reinforcement learning in partially observed systemscited by 70
  11. 2019Finite Sample Analysis of Stochastic System Identificationcited by 67
  12. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
19 more
  1. 2019Learning Linear Dynamical Systems with Semi-Parametric Least Squarescited by 58
  2. 2022Discovering Governing Equations from Partial Measurements with Deep Delay Autoencoderscited by 58
  3. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
  4. 2020Logarithmic Regret Bound in Partially Observable Linear Dynamical Systemscited by 46
  5. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processescited by 41
  6. 2018Spectral Filtering for General Linear Dynamical Systemscited by 37
  7. 2018Learning Contextual Bandits in a Non-stationary Environmentcited by 26
  8. 2020Learning the Linear Quadratic Regulator from Nonlinear Observationscited by 21
  9. 2019Learning Latent Dynamics for Partially-Observed Chaotic Systemscited by 18
  10. 2021Gaussian processes meet NeuralODEs: A Bayesian framework for learning the dynamics of partially observed systems from scarce and noisy datacited by 13
  11. 2019Sample Complexity of Kalman Filtering for Unknown Systemscited by 12
  12. 2020Improved rates for prediction and identification of partially observed linear dynamical systemscited by 12
  13. 2021Operator inference of non-Markovian terms for learning reduced models from partially observed state trajectoriescited by 5
  14. 2021Koopman Spectrum Nonlinear Regulators and Efficient Online Learningcited by 5
  15. 2020Lyceum: An efficient and scalable ecosystem for robot learningcited by 4
  16. 2020Scalable Identification of Partially Observed Systems with Certainty-Equivalent EMcited by 4
  17. 2019Periodic Bandits and Wireless Network Selectioncited by 2
  18. 2019Robust guarantees for learning an autoregressive filtercited by 2
  19. 2021Periodic-GP: Learning Periodic World with Gaussian Process Banditscited by 1

Built on by

Not cited yet.