Dynamic Structure Estimation from Bandit Feedback using Nonvanishing Exponential Sums
Authors: Motoya Ohnishi
Isao Ishikawa
Yuko Kuroki
Masahiro Ikeda
Venue: Accepted by TMLR ()

Abstract: 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.

Published in Transactions on Machine Learning Research (7/2024)
Dynamic Structure Estimation from Bandit Feedback using Nonvanishing Exponential Sums
Motoya Ohnishi*
mobnishhi@@cs..ussinggooo
Paul G. Allen School of Computer Science & Engineering
University of Washington
Isao Ishikawa*
Ehine University
RIKEN Center for Advanced Intelligence Project
Yuko Kuroki
wuko.kurokkiBeeelaa..c.
CENTAI Institute
Masahiro Ikeda
masahiro skeda @rikens.jp
RIKEN Center for Advanced Intelligence Project
Keio University
Reviewed OpenReview: https: https:://ppereeviau
openreview. net/ pet/formm? id= L
Abstract
This work tackles the dynamic structure estimation problems for periodically behaved dis- crete dynamical system in the Euclidean space. We assume the observations become se- quentially available a form of bandit feedback contaminated by sub-Gaussian noise. Under such fairly general assumptions 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 complex- ity bounds for our algorithms, and we experimentally validate our theoretical claims on simulations of toy examples, including Cellular Automata.
the noise distribution, we carefully identify set
1 Introduction
System identification has been of great interest in controls, economics, and statistical machine learning (cf. Tsiamis Pappas (2019); Tsiamis et al. (2020): Lale et al. (2020): Loc (022); Kakade et al. (2020):
Ohnishi al. (2024); Mania et al. )2022); Simchowitz & Foster (2020); Curi al. (2020); Hazan al.
[2018]; Simchowitz et al. (2019) Lee & Zhang (2020)). In particular, estimations of periodic information, including eigenstructures for linear systems, under noisy and partially observable environments,
essen- tial to a variety of applications such as biological data analysis (e.g.. Hughes et al. (2017); (ookolove &
Bushell (1978); Zielinski et al. (2014): also see Furussaw. & Kaneko (2012) for how gene oscillation affects
differentiation of cells), earthquake analysis (e.g., Rathje et al. (1998); Sabetta & Pugliese (1996); Wolfe
( see Allen Kanamori] (2003) for the connections of the Trequencies and magnilude of earthquakes),
Aerts Couillet & Debbah (2011) Derevyanko et al. 2016 6 just to name a few.
chemical/ themical/asteree asteroseismiic analysis (e.g., Aerts et al. (2018 and communication and information systems (e.g..
equal contributions

---

Published in Transactions on Machine Learning Research (7/2024)
In this paper, we focus on the periodic structure estimation problem for nearly periodically behaved discrete dynamical systems (cf. Arnold (1998); specifically, we mainly study theoretical aspects of recovering struc- tural information under a novel set of model assumptions. We allow systems that are not eractly periodic with sequentially available bandit feodback. Due to the presence of noise and partial observability, our prob- lem setups do not permit, the recovery of the full set of seriod/eigenvalues information in general; as such we particularly ask the following question: what subset of information on dynamic structures can be stafisti- cally efficiently eslimated? This work successfully answers this question by identifying and mathematically defining recoverable information, and proposes algorithms for efficiently extracting such information.
The technical novelty of our approach is highlighted by the carcful adoption of the asymptotic bounds on the exponential sums that effectively cancel out noise effects while preserving the information to be estimated. When the dynamics is driven by a linear system, the use of the Weyl sum Weyl (1916), a variant of exponential sums, enables us to extract more detailed information. To our knowledge, this is the first attempt of employing asymptotic results of the Weyl sum for statistical estimation problems, and further studies on the relations between statistical estimation theory and exponential sums (or even other number theoretical results) are of independent interests.
With this summary of our work in place, we present our dynamical system model below followed by a brief introduction of the properties of the exponential sums used in this work.
Dynamic structure in bandit feedback. We define D Rd as a (finite or infinite) collection of arms to be pulled. Tet (ne) be noise sequence. Let θ c Rdd be set of latent parameters. We assume that there exists dynamical system on O, equivalently, map f O + O. At cach time step E (1,2,...), learner pulls an arm 2t E D and observes a reward
re(2,) = (0) T x + T/s,
for some 0 E O. In other words, the hidden parameters for the rewards may vary over time but follow only rule f with initial value 6. The function Ta could be viewed as the specific instance of partial observation (cf. Ljung (2010)).
Brief overview of the properties of the exponential sums used in this work. Exponential sums, also known trigonometric sums, have developed as significant. area. of study in number theory, employing various methods from analytical and algebraic number theory (sec Arkhipov et al. (2004) for an overview). An exponential sum consists of a finite sum of complex numbers, each with an absolute value of one, and its absolute value can trivially be bounded by the number of terms in the sum. However, due to the cancellation among terms, nontrivial upper and lower bounds can sometimes be established. Several classes of exponential sums with such nontrivial bounds are known, and in this study, we apply bounds from a class known as Weyl sums to extract. information from dynamical systems using bandit feedback. Tn the mathematical community, these bounds are valuable not only in themselves but also for applications in fields like analysis within mathematics (Katz) 1990). This rescarch represents application of these bounds in the context of machine learning (stalistical learning/estinnn estimmaiiti problem) and is cast as one of the first attempts to open the applications of number theoretic results to learning theory.
In fact, even the standard results utilized in discrete Fourier transform can be leveraged, with their (non)asympiotic properties, to provably handle noisy observations to extract (nearly) periodic informa- tion. This process is illustratod in Figure | (the one for period cstimation); where we show that one can effectively average out the noise through the exponential sum (which is denoted by R in Figure [ while preventing the correct period estimation from vanishing, By multiplying the (scalar) observations by certain exponential value, the bounds of the Weyl sum (which is denoted by W in Figure [] can be applied to guarantee the survival of desirable target eigenvalue information; this is illustrated in Figure (the one for eigenstructure estimation).
Our contributions. The contributions of this work are three folds: First, we mathematically identify and information when the observations are available in a form noise, which is more general than
define a recoverable set of of bandit. leedback. The feedback is contaminated by a
2

---

Published in Transactions on Machine Learning Research (7/2024)
Period estimation
Correct estimate
R((a))=1ig)) Ej a
Application of Discrete Fourier Transform
Noise Wrong estimate
Eigenstructure estimation
Eigenstructure
W (N, 22 22m
Application of the Weyl sum
Noise
Figure 1: Overview of how the exponential techniques used in the work. For (nearly) period estimation problem, it is an application of discrete Fourier transform in our statistical settings, which ensures that the correct estimate remains while noise effect or wrong estimates are properly suppressed. When the system follows linear dynamics in addition to the (nearly) periodicity, our application of the Weyl sum, variant of exponential sums, preserves some set of the eigenstructure information.
those usually considered in system identification work. Second, present provably correct algorithms for efficiently estimating such information; this constitutes the first attempt of adopting asymptotic results the Weyl sum. Lastly, we implemented our algorithms for toy and simulated examples to experimentally validate our claims.
Summary of technical contributions and challenges. Here, we showcase a summary of tochnical contributions and challenges to be overcome:
Exploiting the exponential sum techniques (including the discrete Fourier transform) studied in mumber theory community filtering within the context of statistical estimation problems.
Adapt the Weyl sum technique to deal with eigenvalues by extending it to matrix sum.
Defining novel mathematical concepts: (aliquot) nearly period and (0, distinct eégenvalues.
Concurrently applying a set of filterings to statistically identify correct periodic structure (we call this as concurrent application of filterings in Algorithm
System recovery through maintenance of isomorphic structure in observation (we call it isomor- phicily mainlenance lemma; see Lemma C.1
Notations. Throughout this paper, R, R20. N, Zso, Q. Qxo. and C denote the set of the real numbers, the nonnegative real numbers, the natural numbers (10, 1,2,.. the positive integers, the rational numbers, the positive rational numbers, and the complex numbers, respectively. Also, [T] := f1.2.... for Z The Euclidean norm is given by ||œ]|æ> = (x, (). VxTa for x E Rd, where (-) stands for transposition. ||M]| and [|M |r are the spectral norm and Frobenius norm of a matrix M respectively, and (MM) and (MM are the image space and the null space of M, respectively. a.b. The floor and the ceiling of a real number a is denoted by [a] and [a], respectively. Finally, the least common multiple and the greatest common divisor of set C of positive integers are denoted by lcm(E) and gC), respectively.
is a divisor of 6, is denoted by
3

---

Published in Transactions on Machine Learning Research (7/202/)
Throwing dice many times and compute the arithmetic
Averaging the states over long horizon may produce the outputs
Convergence of arithmetic mean
Fixed point attractor
Limit cycle attractor
3.0
2.0
(0,0)
10
-1
Eeraitons
Figure 2: Illustration of of dynamic information through concentration measure. Left: An example of the law of large numbers showing the sample mean of the numbers given by throwing dice many times will converge towards the expected value as the number throws increases. Right: An intuitive understanding of how concentration of measures process of averaging information; in this case, the dynamics on the left side fixed point attractor and the right one limit cycle attractor, both of which may return (0, 0) when averaging the states over long time.
the observations may erase not only the noise effect but also the dynamics
2 Motivations
As our main body of the work is largely theoretical with a new problem formulation, this section is intended to articulate the motivations behind this work from scientific (theoretical) and practical perspectives followed by the combined aspects for our formulation.
2.1 Scientific (theoretical) motivation
When dealing with noisy observation, it is advised to use concentrations of measure to extract the true target value by averaging out the noise effect over sufficiently many samples. On the other hand, when the samples generated by a dynamical system, averaging over the samples will have effect of averaging over time, which could lose some information on the evolution of dynamics.
Dynamic information recovery from noisy observation. Consider for example a fixed point attractor and a limit cycle attractor dynamics as depicted Figure 2 when averaging over samples generated by sufficiently long time horizon, both cases would output values that are close (0, which ambiguates the dynamical propertics. In particular, properties of long-time average of the dynamics have been studied in ergodic theory (cf. Walters (2000)). ) and studying dynamical systems from both time and measure is of independent interest.
Dynamic information recovery from scalar obsorvations. Also, linear bandit feodback system is a special case of partially observable systems, and specifically considers scalar (noisy) observations.
For reconstruction of attractor dynamics from noiseless scalar observations, will be mentioned in Section Takens' theorem (or delay embedding theorem; Takens (1881)) is famous, where an observation function is used to construct the embedding. It identifies the dynamical system properties that are preserved through the reconstruction as well.
If the noise also present, the problems become extensively complicated and some attempts on the analysis have been made (Casdagli et al. 1991}; which discusses the trade-off between the distortion and estimation errors.
2.2 Practical motivation
Practically, periodic information estimation is of great interest as we have mentioned Section in addition, eigenvalue estimation problems are particularly important for analyzing linear systems.
4

---

Published in Transactions on Machine Learning Research (7/2024)
Physical constant estimation. Some of the important linear systems include electric circuits and vi- bration (or oscillating) systems which are typically used to model an effect of earthquakes over buildings. Eigenvalue estimation problems in such cases reduce to the estimation of physical constants. Also, they have been studied for channel estimation Van De Beck et al. 1995 as well.
Dynamic mode decomposition. At the same time, analyzing the modes of a target dynamical system by the technique named (extended) dynamic mode decomposition ((E)DMD; ef. Tu 20013 Kutz et al. (2016);
Williams et al. (015)) has been extensively rescarched. The results give spectrum information about the dynamics.
Attractor reconstruction. With Takens' theorem, obtaining dynamic structure information of attractors in dinees-imeniional space from finite number of scalar observations is useful in practice well; see (Bakarji et al. 2022) for an application in deep autoencoder. Our problems are not dealing with general nonlinear attractor dynamics; however, the use of exponential sums in the estimation process would become a foundation for the future applications for modeling target dynamics.
Communication capacity. There has been interest of studying novel paradigms for coding, trans- mitting, and processing information sent through optical communication systems (Turitsyn et al. 2017); when encoding information in (nearly) periodic signals to transmit, computing communication capacity that properly takes communication errors into account is of fundamental interest. If the observation is made as a mix of the outputs of multiple communicttio channels, the problem becomes relevant to bandit feedback as well.
Bandit feedback single-pixel camera. As widely studied in context of compressed sensing (cf. Donoho (2006) Eldar & Kutyniok (2012); Candes et al. (2006)), reconstruction of the target image from the single-pixel camera (e.g., Duarte et al. (2008)) observations relies on a random observation matrix (or vector) to obtain a single pixel value for cach observation. It is advantagoous to concentrate light to one pixel for the cases where the light intensity is very low. Bandit feedback naturally coincides with random observation matrix that the user can design. The observation through random matrix coupled with compressod sensing has been studied for channel cstimation, magnctic resonance imaging, visualization of black holes, and vibration analysis as well.
Bandit feedback recommendation system. Reward maximization problems from bandit feedback have been applied to recommendation system (c.g., [i al. (010)) for example, where the observations are in scalar form. Other applications of bandit problems include healthcare, dynamic pricing, dialogue systems and telecommuiccttios. Although our problem formulation is not meant maximize any reward, it is seamlessly connected to the bandit problems as described below.
Connection to reward maximization problems. As we will briefly describe in Appendix L thanks to the problem formulations in this work, one could use our estimation algorithms for downstream bandit prob- lems (i.e., reward maximization problem with bandit. feedback). A naive approach is explore-Ihen-commii type algorithm (cf. Robbins (1952); Anscombe (1963) where the "explore" stage utilizes estimation mechanism to identify the dynamics structure behind the system paramcter. Devising efficient dynamic structure estimation algorithms for other types of information than the periodicity and eigenstructure under bandit feedback scenarios may also be an interesting direction of research.
2.3 Combined aspects
In our work, we essentially consider periodic (and eigenstructurr) information recovery from observation data, which as mentioned crucial some application domains. In particular, our formulation cares about the situation where the observation is made by bandit foedback which produces a sequence of scalar observations. We mention that the bandit feedback is essentially just (noisy) scalar observation where (possibly random) observation vectors selected by users.
5

---

Published in Transactions on Machine Learning Research (7/2024)
sequence of observations as vector
target
random filter
periodic motion
Figure 3: Illustration of the example practical case where techniques may be applied; in this example, the target object is following nearly periodic motion, and requires concentration light to be captured. random filter could be employed and observe single value sequentially to predict its periodic information.
One possible example scenario in which bandit feedback and dynamic structure estimation meet. is ralustrated in Figure where the target system has some periodicity and the noisy observation is made through a single- pixel camera equipped with a random filter to be used to determine the periodic structure of the target system.
Also, as mentioned, we emphasize again that reconstruction of dynamical systems characteristics such their attractor dynamics through (noisy, user-selected) scalar observation is an important area of research; we believe the use of exponential sums in the reconstruction of dynamics opens up further research directions and applications in similar manner to Takens' theorem (see Section 3 as well).
3 Related work
As we have seen Section our broad motivation stems from the reconstruction of dynamical system information from noisy and partial observations. The most relevant lines of work this problem are (1) that and its extensions, and (2) system identifications for partially observed dynamical
of Takens (Takens 1981 systems.
While the former studies more general nonlinear attractor dynamics from sequence of scalar observations made by certain observation function having desirable properties, it is originally for the noiseless case, Although there cxist some attempts on extending it to noisy situations (c.g.. Dasdagii et al. (1991]), provable est estimation of some dynamic structure information with sample complexity guaranlees (or nonasymplolic result) under fairly general noise case is not elaborated. On the other hand, our work may be viewed special instance of system identifications for partially observed dynamical systems. Existing works for
sample complexity analysis of partially observed linear systems (e.g.. Menda et al. 2020 Hazan et al. (2018)
Simchowitz et al. (2019); Lee & Zhang (2020): Tsiamis & Pappas (2019): Tsiamis et al. 20200: Tale et al.
b2 Lee (2022 Adamns et al. (2021)) Bhouri & Perdikaris (2021): Ouala et al. (2020)
Cy & Peherstorfer 2021 9 Subramanian et al. (2022): Bennett & Kallus (2021): : Lee et al. (2200)) typically consider additive
Gaussian noise and make controllability and/or observability assumptions (for autonomous case, transition
with Gaussian noise with positive definite covariance is required). While (Mhammodi et al. 2020) considers nonlinear observation, it still assumes Gaussian noise and controllability. The work (Hazan et al. 2018)
considers adversarial noise but with limited budget; mention its wave-filtering approach is interesting and our use of exponential sums could also be viewed as filtering. Also, the work (Simchowitz et al.) 2019) considers control inputs and bounded semi-adlversarial noise, which is another set of strong assumptions.
Our work based on the different set assumptions and aims at estimating a specific set information: i.c., while we restrict oursclves the case of (nearly) periodic systems and allow observations in the form of bandit feedback, our goal is estimate (nearly) periodic structure of the target system. this regard, we are not proposing "better" algorithms than the existing lines of work but considering different problem

---

Published in Transactions on Machine Learning Research (7/2024)
noise
observation
control
adversarial bounded & limited budget
sub-Gaussian
nonlinear linear
observability assumption for linear system
autonomous
control that linearly evolves state
Gaussian
noiseless
smooth / typical scalar-valued
user-defined linear (scalar) feedback
controllability assumption linear system
dynamical properties to be reconstructed
nonlinear
smaller than one spectral radius
attractor
dynamics
linear
example of Takens'
(nearly)
periodic
our focus
Figure Illustration of the position of work as study of reconstruction of dynamical system properties. We assume sub- Gaussian noise, bandit feedback (user-defined linear feedback contaminated by noise), autonomons system, and (uearly) periodicity which is information be extracted. our kuowlodge, our assumptions not subsume or subsumed by those of other work as problem of provably estimating periodic structure. In comparison to existing system identification techniques partially observed dynamical systems, we do not assume Gaussian (or bounded) noise, limited budget for adversarial noise, controllability, observability noisy transition, while we assume bandit feedback to identify a recoverable set of dynamic structure information.
setups that we believe are well motivated from both theoretical and practical perspectives (see Section 2). We mention that there exist many period cstimation methods (c.g.,Moort et al. (2014); Tenneti & Vaidyanathan (2015)), and the case of zero noise, this becomes a trivial problem. For intuitive understandings of how our work may be placed in the literature, we show the illustration in Figure
We also mention that model of bandit feedback is commonly studicd within stochastic linear bandit literature (ef. Abe & Long (1999] Auer (2003) : Dani et al. (2008) Abbasi-Yadkenn et al. (2011)). Also, as we consider the dynamically changing system states (or reward vectors), it is closely related to adversarial bandit
problems (e.g., Bubeck & Cesa-Bianchi
(2012) Hazan (2016)). Recently, some studies on non-stationary
rewards have been made (cf. |Auer et al. 2019 Besbes et al. (2014): Chen et al. (2019): : Cheung et al. (2022): Luo al. (2018) Russac et al. (2019b rovo et al. (2020); ; Wu al. (2018)) although they do not. deal with periodically behaved dynamical system properly (see discussions in (Cai al.) 2021] well). For discrete action settings, (Oh al.) 2019) proposed the periodic bandit, which aims at minimizing the total regret. Also, if the period is known, Gaussian process bandit for periodic reward functions was proposed (Cai et al, 2021 under Gaussian noise assumption. While our results could be extended to the regret minimization problems by employing our algorithms for estimating the periodic information before committing to arms in a certain way, we emphasize that our primary goal is to estimate such periodic information in provably efficient ways. We thus mention that our work is orthogonal to the recent studies on regret minimization problems for non-stationary environments (or in particular, periodic/scasonn environments). Refer (Lattimore & Szeeesvári 2020 for bandit. algorithms that not covered here.
4 Problem definition
In this section, we describe our problem setting. In particular, we introduce some definitions on the properties of dynamical system.

---

Published in Transactions on Machine Learning Research (7/2024)
4.1 Nearly periodic sequence
First, we define general notion of nearly periodic sequence:
Definition 4.1 (Nearly periodic sequence). Let (X,d) d) be a metric space. Let μ 0 and let L E Z20- We say sequence (We) X' is j-nearly periodic of length L if d(ys+Lt, vo) < μ for any 8, t Zzo- We also call L the length of the p-nearly period.
Intuitively, there exist L balls of diameter j in X' and the sequence y1 92.... moves in the balls in order if (ye)(= is y-nearly periodic of length L. Obviously, nearly periodic sequence of length L is also nearly periodic sequence of length mL for any E Z200 We say a sequence is periodie if it is O-nearly periodic. We introduce notion of aliquot nearly period to treat estimation problems of period:
Definition 4.2
Assume sequence {2 C X is y-nearly periodic of length L for some μ 2 0 and L E Zzo A positive integer l is a Aplliual nearly period ((p, a))m of ( if f and the sequence (gr e is -naaal periodic.
(Aliquot nearly period). Let (X, d) be metric space. Let p 0 and 2 1.
We may identify the (p. annpp with 2ea-nearly period under an error margin p. When estimate the length L of the nearly period of unknown sequence (Ue)e, we sometimes cannot determine the L itself, but an aliquot nearly period.
Example 4.1. A trajectory of finite dynamical system is always periodic and it is the most simple but important example of (nearly) periodic sequence. We also emphasize that if we know the upper bound of the number of underlying space, the period is bounded above by the upper bound as well. These facts are summarized in Proposition 4.1 The cellular automata on finite cells is a specific example of finite dynamical systems. We will treat LifeGame Conway et al. (1970). a special cellular automata, in our simulation experiment (sec Scction 6).
Proposition 4.1.
Let f O + θ
be a map on a set O. If [ < co, then for any t 2 |+| and 0 E O
(0) = (0) for some
S L < |0).
Proof. Since (0, ....)....................... | (0) > 10), there exist < S |0| such that f'(0) (0) by the pigeon
hole principal. Thus, f0 for all i 1 |0).
If linear dynamical system generates nearly periodic sequence, can show the linear system has specific structure as follows:
Proposition 4.2. Let M Rd + Rd be a tinear map. Let Cd = Va be the decomposition vio generalized eigenspaces of M, where a runs over the eigenvalues of M and Va = (Nal - M) Assume that there evisls 0, for any 0 E Rd, (M' is u-nearly periodic for some to E N. Let 0 = E. 0. @..o. Then, each eigenvalue a such that 0, # 0 satisfies |a| S 1, in addition, la = 1 and 0, # 0, MO, = al..
Proof. We note that {M'o is bounded for any v E Rd by the assumption on M. Thus, M cannot have an eigenvalue of magnitude greater than 1. We show that a is in the form of a = _220q for some q E Q if |a| 1. Suppose that a = elar for an irrational number 7 E R. Then, for an eigenvector w for 0, with ||ll| > p. W cannot become a p-periodic sequence. Thus, we conclude a .'2mq for some q E Q Next, we show MO.- a0,, if |a| = 1 and 0., # O. Suppose (M aT)O,, # O. Since (M al)²0, = 0, there exists 1 < d' < d such that (M- ad) 0a = 0 but (M - al)dda 0a # O. Let w' : (M a dd' -0... Then, we see that (M - aT) = O but (M al)w ' + O. By direct computation, we see that
| [I(M aI + wd) 2 C](M ad) ||00
Thus, we have || 1ل + 00 as + oo, which contradicts the fact that [M''whes is a bounded sequence. The last statement obvious.
Let W be a linear subspace of Cd generated by the trajectory (M0, M and denote dim(W) by do- Note that restriction of M to W induces linear map from W to W. We denote by Mg the induced linear
8

---

Published in Transactions on Machine Learning Research (7/2024)
map from W to W. Let W BaEA a be the decomposition via the generalized eigenspaces of Me, where A is the set of eigenvalues of Mo and Wa == ((aa MM)ddu) We define
W=1 = 0/a/=1 Wa. W<1 == 0|a|<1 Wa-
Then, we have the following statement as a corollary of Proposition 4.2 Corollary 4.3. There enist linear maps M1, Me1 W - W such that
1. Ma = M1 + Ma1;
2. Mi M<M M1 = 0,
M1 diagonalizable and any eigenvolue of M1 is of magnitude 1, and
4. any eigenvalue of Me1 is of magnitude smaller than 1.
Proof. Let p W + W=1 be the projection and let i W=1 - W be the inclusion map. We define M1 == iMp.. We can construct Mr1 in the similar manner and these matrices are desired ones.
Example 4.2. Let G be finite group and let p be finite dimensional representation of G, namely, group homomorphism p: G - GLm(C), where (C) is the set of complex regular matrices of size m. Fix E G. Let B E Caxn be a matrix whose eigenvalues have magnit udes smaller than 1. We define a matrix of size m + n by
p(g) 0
00 B )
M:
Then, (M'x) is p-nearly periodic sequence for any > O, E Cm, and sufficiently large to- Moreover, we know that the length of the nearly period is GG). We treat the permutation of variables in Rd in the simulation experiment (see Section 6), namely the case where is the symmetric group Ga and is a homomorphism from to GLa(C) defined by p(g)((z))}=)) = (Ig0)) which is the permutation of variable via g-
4.2
Problem setting
Here, we state our problem settings. We use the notation introduced in the previous sections. First, we summarize our technical assumptions as follows:
Assumption (Conditions on arms). The set of arms D contains the wiil lyppersphere
Assumption 2 (Assumptions on noise). The noise sequence {m conditionally R-sub-Gaussiae (R e R2d), Le.,, given t,
ve R, EE [e $
22
and E[n:FF-11] 0, Var(n|FF-1 S R², where (Fr) an ascending family and we assume that 21...., 21,...,Ir41, ......,7, T7r are measurable with respect to F,. Assumption (Assumptions on dynamical systems). There erists μ > such that for any f O the sequence (f) is y-nearly periodic of length L for some to E N. We denote by Bg the radius of the smallest ball containing (f)(
Remark 4.4. Assumption excludes the lower bound arguments of the minimally required samples for work since taking sufficiently large vector (arm) makes the noise effect negligible. Considering more restrictive conditions for discussing lower bounds is out of scope of this work.
Then, our questions are described as follows:
Can estimate the length from the collection of rewards (rr():)) efficiently ?

---

Published in Transactions on Machine Learning Research (7/2024)
Algorithm Period estimation (DF')
Input: Current time lo E Zzo; Tpi > 0; Lmmax > 1; orthogonal basis { {u
ua} of Rd
Output: Estimated length L
+ 1; [8 +
for m =1....,d do
for t- lo, ,,..,, to + Tp do
Sample arm um and observe re um 5: end for
6: while B- < Limax do
7: (
8:
for (s, = (0,
(0, (4.. 1,6 1) do if R (Ita+s= (ens=ss(mmml:e ( :6/
> then
10:
8 - BL f+1
11:
12:
Break
13:
end if end for
14:
15:
end while
16: to - to + T
17: end for
18: t 3
If we assume the dynamical system is lincar, further obtain the cigenvalues of f from collection of rewards ?
How many samples do we need to provably estimate the length L or eigenvalues of f
We will answer these questions in the following sections and via simulation experiments.
5 Algorithms and theory
With the above settings in place, we present a (computationally efficient) algorithm for each presented problem, and show its sample complexity for estimating certain information.
5.1 Period estimation
Here, we describe an algorithm for period estimation followed by its theoretical analysis. The overall pro- cedure summarized in Algorithm [ Line S executes concurrent application of filterings. To analyze the sample complexity of this estimation algorithm, first introduce an exponential sum that plays key role:
Definition 5.1. For a positive rational number g E Q and T complex numbers 01,...,07 Or E C, we define
R((a)) = a 2ngg
For a p-nearly periodic sequence a = (a of length I, we define the supremum of the standard deviations of the L sequential data of a:
to+ 1-1 L
to+ 1-1
(L(a) ;= sup
a1
21
L
1=
j= to
10

---

Published in Transactions on Machine Learning Research (7/2024)
The exponential sum R(::)) can extract divisor of the nearly period of p-nearly periodic sequence if j is "sufficiently smaller" than the variance of the sequence even when the sequence is contaminated by noise: more precisely, we have the following lemma:
Lemma 5.1. Let (a,) a p-nearly periodic sequence of length L. Then, we have the following statements:
if L 1, then there erists Z00 with L such that
0² 2400
Lsup121 l
R (1))
(5.1)
2. if 3 is not a divisor of L, then for any a E Z>o;
L2Coll + sup la.))
R ((aa))==1))33) < sut
(5.2)
T
where Co := 1 o 112
Proof. As (a)) is p-almost periodic, there exist (b:) of period L and (a)i=1 with suP121 leal < such
that ag = b + Ct.
First, we prove 5.1
Let
1
b: L 1=1
bys
by
b
22tg
(q E Q).
I.
t=1
We claim that
L sup(16//21 12]
b
ba/L
2
1 Σ
bb.
612 2 0² -240.
(5.3)
L
In fact, the first inequality obvious. The equality follows from the Plancherel formula for finite abelian Excercise 6.2)). As for the last incquality, take arbitrary to Z and
group (sce, for example, (Serre 1977
define â I Eisto f6--1 ar and ē
I,-
L--
t= G. Then, we have
L
4o+L-1
Lo+L-1
la+t L-1
lbe 812 2
aa - a|²
+
Ce 2
la al la - c
L
L
t=
4o+1-1
lo+L-1
a4 a|² +
C 2
t=to
t=fo
1o+11
1-+--1
2
la: - -ā/2.
la
2/2
L
1=1p
1=
to L-+
2
|a - x|2 2110.
Here, we used the Cauchy-Schward inequality the second incquality. Since to is arbitrary, we have 5.3 Let E argmax 16 and let == s/L. Let T= LT + ry for some T, E N with s y L.
Then, we have
T
I.
Lsup lael
R ((a)))
2
a 12mqs
T
T
1=0
1=1
supp2> lal
16,
4
T
0
2110
Lsup od
L
L
T
11

---

Published in Transactions on Machine Learning Research (7/2024)
Next, prove 5.2) As in the same computation above, have
LT
T
L suup lael
R ((a
v
22alt//8
a 2
a
+
T
T
L
T
t=
LT
T
L Luuprso lad
220o1/33
bee 2
+ 12
T
T
T
t=
a=1
(u+sup laal 121
L Lsupisolu lael
T
+ 1
e
T
Since |1 222ma|
2 12(11 d²)x²/ for E (0, by Chosneau & Bagul
2020
Proposition 3.2), we have
R 1//11 < (1 sup lael
28L
Supp21 ldd
+ u
121
v2(3/4)a2/0T
T
LBCo(u sup (a:l)
T
Then, we obtain the explicit lower bound of the samples for period estimation:
Proposition 5.2. Let (at) be μ--nearly periodic sequence of length L. Fix positive integer Lmmax > 1 with L < Imax, 8 (0, E 1), and on > 0. Lel (mt) be noise sequence salisfying Assumption Put = 1/(1+ / /Lmxx + I) and X = p/(007)) We define
E = ooYE.
If (/(((E)) < <0 S (a)),,, then, for any
8 8Lmax R22 log(4/0)
36T5/2 sup lae|
T T2
+
og(E - A)2
oolE A)
the set of rational numbers
Sr. := {q (0,1) : 9L E Eso and |R ((ar + m))==ii)) > E}
is non-empty with probability at least 1-6
If we apply several collections of rewards (ra(=r)) for sufficiently large T indicated in Proposition 5.2 obtain various divisors of L. Finally, provide the precise inputs and output of Algorithm in the following Theorem:
Theorem 5.3.
Suppose Assumplions 7 and 3 hold. Let r E [0,1) be a non-negative real number, and suppose > and E (0,1) are given. Fix a positive integer Linax with I Lmax- We define
(5.4)
6 d
Assume that p.. Let Tp be an integer satisfying
72dAL2 max
108Ba V dL3
To 2 p² r)2
max
(5.5)
p(1
where A= 122 log(4d log Lmxx/8). Then, the output L of Algoritimm is (p, Vd)-anp of ()) with probability at least 1 8.
If is sufficiently small, we may set as small positive number, in particular r = 0 if the system is periodic. Remark 5.4. If random arm selection is adopted rather than the orthogonal basis, it may undercstinate an error margin on some dimensions, which could lead to the nearly period with much larger error margin than expected; considering failure probability of such case may potentially produce a variant of our algorithm.
12

---

Published in Transactions on Machine Learning Research (7/2024)
Algorithm 2 Eigenvalue estimation
Input: Effective sample size N E Z threshold 7(N)
Output: Matrix (1
Independently draw random unit vectors Tm. m [d], from uniform distribution over the unit sphere in R
Wait. N time steps.
for t = N + 1,... .N + 2Nd do
4: mo + [(t N -) mod 2d +1
5: + | 2d]
6:
Sample arm I2 = im and observe 7g = re(mm).
7: end for
Construct matrices (N and (N) as in (.6), respectively.
Obtain the low rank approximation (N(N) of (N(N) via SVD with the threshold 7(N..
10: Output (No))
5.2 Eigenvalue estimation
If the underlying system has certain structures, more detailed information about the system expected be obtained. In this section, we assume the following condition, linearity of the underlying dynamical system f O, in addition to Assumption
and 3
Assumption (Linear dynamical systems). The dynamicaal system f - linear and is represented by a matriz M Rddd
Let Cd = G. Va be the decomposition via generalized eigenspaces of M, where a runs over the eigenvalues of M and V = ((all M))). We describe 0 = E., 0a with O₂ E V.- We remark that an eigenvalue a of M such that 0. # 0 is in the form of 2 unless |a| < 1 by Proposition 4.2
Our objective is to estimate some of, if not all of, the eigenvalues of M with high probability within some error that decreases by the sample size. To this end, we define the meaningful subset of eigenvalues of M.
Definition 5.2 ((0, didttiinct eigenvalues). For a vector 0 E Cdd and Z we define a (0, ki-distinct eigenvalue by cigenvalue of M such that [3] and 0gg # 0.
In our case, starting from a vector 0, the effect of the eigenvalues that are not of (0, dis-tiiic eigenvalues of M may not be observable. Basically, once being able ignore the effects of eigenvalues of magnitudes less than 1, the system becomes nearly periodic and aim at estimating (0, d)-distinct eigenvalues obtain more samples.
Our eigenvalue estimation algorithm is summarized in Algorithm 2 it maintains the following matrices. For E Z>u, d random unit vectors $1...., Zd, and s = 0, 1, we define the matrix A,(N) E Cd so that its (k, E) element is given by
......,de
T2(k- 12(k-1)d+sd (dk- 2n72
(5.6)
That is, after N steps, the reward multiplied by exp(i2r)//4L) is placed from the top row of Ag and then the top row of AI, followed by the second rows of them, and so Then, those values summed up for every 2d steps or every jth cycle. Here, after throwing away N samples, the effects of eigenvalues of magnitude less than become negligible, and the trajectory becomes nearly periodically behaved under Assumption
The rest of the samples is used to average out the observation noise while maintaining some meaningful information about M.
The aforementioned exponential sum can be characterized by the Weyl-type sum of matrices, key machinery for our algorithm, which we define below:
13

---

Published in Transactions on Machine Learning Research (7/2024)
Definition 5.3. Let W be linear space and let Mi...., My for N Z>o be linear maps W. For I. E Zyo, we define
N 22
W ((M MN)) = N M
Remark 5.5. Let Ean = M+ddi+++s+++++o (hudh- be a noise matrix for 8 = 0, 1. Let
I M
22 226+1
X ==
and K ==
Then, A.(N) has an alternative description as follows:
A.(N) XX ( M Mad+N-IK W ((Era))
(5.7)
As in Proposition 5.7 below, the Weyl-type sum has a crucial property. Define by
k: inf (||P||| P-1 JM..
where JM is Jordan normal form of M. Also, we define A (0, 1] to be value such that, for any eigenvalue of M satisfying |a| < 1, |a| < 1 A (define A = 1 if no such eigenvalue exists). Note by Proposition 4.2. the existence of such spectral gap is guaranteed without any further assumptions.
Roughly speaking, Algorithm 2 estimates AoN) = XM Of course, the formula in is not valid as X, K, and the Weyl-type sum sum are not necessarily invertible and we cannot recover full information of 2d in general. However, we can still reconstruct information of Md restricted the cigenspaces for (0, d)- distinct eigenvalues.
To this, introduce the Weyl sum and its lower bound: Lemma 5.6 (Lower bound the Weyl sum
Bourgain
1993 Oh
Define the Weyl sum by
N
W WNN,b, ()). =
2n
28 + +)) au
1=0
for some b b N, q E Zso, b and N Zzo. Then, for N > 16q2, it holds that
(N,
Proof. It is immediate from Proposition 3.1 in Oh because ged(1, 4g) 1, 4g 0 mod 4, and 2b is even. 0
We define Cws(L) > 0 by
(L) = inf p20000- N (N < for any N 1612,0
Then, we have the following proposition:
Proposition 5.7. Let M1 and Me1 be matrices as in Corollary 4.3
We define linear maps on W by
QN(M) = == ((M22) 11
QN(M21):= := (1M22 1))0)))))
((M2f))NN))
Then, we have the following statements:
14

---

Published in Transactions on Machine Learning Research (7/2024)
W (MM
(M ))==) = (M1 + (N(M,)),
for any N Z 16L2, QN (Mi) is invertible on W=1,
3. for any 2 0 and for any N 2 16L2,
S <C (L),
4- for any 2 2(d 1), we have
M ON PeRe-Air-de
NAd-1
Proof. We prove By the properties and 2 in Corollary 4.3 we have W ((M2d))) )oo') = Qx(M) + QN Next, we prove
2 When we regard QNv (Mi)lw as a linear map on W=1, it represented as a diagonal matrix diag( W (N, b1, L).... (N, bn, L)), where m = dimW=1- Therefore, by Lemma 5.6
(x) is a bijective linear map W-1- Next, we prove 3 We estimate [[M[QN(M)) Let p: Cd - W
be the orthogonal projection and let i: W - od be the inclusion map. Let M1 == iM Caxd, Then, we have
[Q = 11Q (MiIl S (L).
Next, we estimate I )I. Let Mc1 := iM Then, iM;: (Mci)p= w ((A22) strffttt)gf )=))) and QN (M<1)ll- Let P be regular matrix such that
Ma = PJP-!
where J the Jordan normal form. Then, for r 2 2(d 1), we see that
QN (Ma1)l = CN
N
dx
[2d +r
K
22
d-1 ) (1 - A)2
N
N
j=n
d'
n11
A) A
d Re A(r-d+1)
A
NAd-1
The second last inequality is proved as follows: for |a| < 1, > and 2 m 2 0,
nj +
1 d
a
m
nitt
1=0 m
ml. drm
f=0
r!
|a| mj di 1
m!
(r m + j)!
da: 1 - x."
==
m
r!
j!la|--m+
m
rr)
|a ir m-
m!
j
(r
+ j)! (1 |a|)3
|a))
jm
where, the last inequality follows from
d
mlç² I-n
m!
I (1 |x] )m
dr
1 20
no( - x: m
Thus, we have
|a mm
()) (1 |a| |a|
) -
3
|a r r-m
Σ 1=0
S |m
()
(1 رaا)
(1 |a| )m
15

---

Published in Transactions on Machine Learning Research (7/2024)
plays essential role in analysis and guarantees that the information in A₂(N) about (0, d)--distintt eigenvalues does not vanish while noise effects are canceled out. Now, state our main theoretical result for the eigenvalue estimation algorithm. Before stating the theorem, we introduce lower rank approximation via the singular value threshold.
Proposition 5.7
Definition 5.4. Let A E Cn be a matrix. Let A = U(D be singular valued decompo- sition of A where U E Cn and V E Cm are unitary matrices and D == diag(o)....,....
is a diagonal matrix with nonnegative components. Let 7 > We define a low rank approximation A, of A via the singular value threshold y by the matrix A, defined by A, = U (D, O) where, Dy d (1,00)())))) (,,00 o²) and 1, is defined to be the characteristie function supported
1 C I.
Given this definition, ready to present the following main result:
Theorem 5.8. Suppose Assumptions 1 2
and hold. Given ô (0, 11, let the effective sample size
max 1672, -(d 1) A log (gg()nn)) d + + d
(5.8)
A
and 7(N) (V4dR R log (8) + 1)//N. Then, there exists matrix A whose eigenvalues are zeros
ezcept for (0, d) distticc eigenvalues of M, such that the output of Algorithm i.e. Ao())) satisfies,
with probability at least - 6, that
(IN)(NN) s c
c( (
[R2 R (log (1/8) + 1)+11
(5.9)
VN
Here, Ao(NNt the Moore- Perrreee pseudo inverse of a lower rank approzimation of Ao(N) via the singular value threshold (NN). The conslant C >>0 depends on 0, M, d, (ām))==) and (w.)
We mention that by using the results shown in Song (2002), the bound on spectral norm 5.9 can be translated the bounds on cigenvalues, where the constant depends on the form of A. As described Theorem 5.8 the constant is not the absolute constant for any problem instance but depends several factors; however, for the same execution, this rate is useful to judge how many samples collects to estimate cigenvalues.
Remark 5.9. We note that the following trick: Fix non-negative integer r 2 O. Take d + r random unit vectors .,,..., Tatr- Then, for = 0, 1, we may define a matrix A,(Nir) ((d+r)x(d+r) so that its (k, E) element is given by
reconstruct the (0, 1)-distinct eigenvalues of M via Algorithm using
120-11144h1- (Zx)e $250 42
Then, we see that Algorithm 2 outputs a matrix Á(r) that well approximates the (0, d+rr-dissinne eigenvalues of M since the matrix A, (N:r) coincides with ANNN) in the case when we replace M and 0 with M(r) and (r) defined by
M(r) = ( M o Clatr)x(tt)0000 0()) == (()):=
(-)) Cdtr.
0 o
Let r be an integer such that r d prime to and fix a positive integer m such that m(r+d) = mod Then, the eigenvalues of A(r) is close those of (0, 1)-distinet eigenvalues we take sufficiently large N.
6 Simulated experiments
In this section, we present simulated experiments that complement the theoretical claims. In particular, conducted period estimations for instance of LifeGame Conway al. (1970), which is special case
16

---

Published in Transactions on Machine Learning Research (7/2024)
14
Figure 5: Left: Illustration of period eight instance LifeGame; (top) original transitions. (down) an instance of noisy observation. Right: j-nearly periodic dynamics (6.1.
of cellular automata Von Neumann et al. 1966), and for nearly periodic toy system, and an eigenvalue estimation for a linear system, where some dimensions are for permutations and the rest is for shrinking.
Period estimation: LifeGame. We use a specific instance of LifeGame which is illustrated in Figure 5 As shown on the top eight pictures, starting from certain configuration of cells, shows transitions of period eight. The sample size is computed as the smallest integer satisfying (5.5). and the threshold æ is given by (5.4). To prevent the dimension from becoming too large, used five cells that correctly display period eight; that is d 5. Noise Nu is given by i..d. Gaussian with proxy R = 0.3,, and the down eight pictures of Figure 5 are some instances of noisy observations. We tested 50 different random seeds (i.e., 1, 51, 101, 151, ... 2451), and computed the error rate (the number of runs producing a wrong estimate other than the fundamental period eight, which is divided by 50); and it was zcro
Period estimation: Simple y-nearly periodic system. We consider the following j-nearly periodic system that circulates over circle with small variations:
Te41 = 11
a
rtt -
Pi [a
1-11-1 +1, /
o.41 =0,+ L'
2m
(6.1)
1
where r and & are the radius and angle, and a of Q. We use μ = 0.001, == 5, and a x. Noise Te is drawn i.i.d. from the uniform distribution within [- R, R] for R == 0.3. We tested 50 different random seeds (ie.. 1, 51, 101, 151, ... 2451), and computed the error rate; and it zero
Eigenvalue estimation: Permutation and shrink. We use d d= 5, and M E R5x5 is made such that 1) the first four dimensions are for permutation (i.e., each of row and column of 4 x 4 sub-matrix has only one nonzero element that is onc.), and 2) the last dimension is simply shrinking: we gave 0.7 for (5, -lelement of M. Initial vector Og and each arm Tm, m E [d], are uniformly sampled from the unit sphere in RR5. The value L is computed by 4! 24. We used the smallest integer N that satisfies (5.8), multiplied by Cam > O. The results are shown in Table [ it is observed that the more samples we use the more accurate the estimates become to (0o. 5)-disinnct cigenvalues of M. Noise ne is drawn i.id. from the uniform distribution within [ R. R] for R = 0.3, and the Table D is of the random seed 1234. We also tested 50 different random seeds (i.e., 1, 51, 101, 151,
2451) for Csim = =30, and computed the mean absolute error between the true (fg, 5)ddisiitt cigenvalues and their nearest estimated values; it was 0.0019, which is sufficiently small.
Attempt on applications to more realistic data: Worm simulation. Finally, we present an attempt on applications to more realistic situation, which will demonstrate some of the important aspects that need to be taken into account when naively applying algorithms to the real world problems. In particular, use OpenWorm (lttps://openworm.ogg than around 10 hours for simulations); example images from this simulation is shown in Figure x (left). It is known that the behavior of worm has some periodicity (e.g., Ahamed et al. (2021)). We resized the images to 6 3x6 6 (i.e., d = 36), and downsampled the video by extracting one per eight images. Also, we repeat the same video the way that the entire vidco still shows smooth flow (i.c., cut the vidco so that the end image is similar to the image in the beginning, and concatenate the same videos) so that we can sample a large number of data.
(Szigeti et al. 2014 to simulate worm motion (we ran more
17

---

Published in Transactions on Machine Learning Research (7/2024)
Table Results for the eigenvalue estimation. The top-most row shows the true eigenvalues M and the second row shows its (0v. 5)-ditiitt eigenvalues. From the third to sixth row, it shows the estimated eigenvalues for different. values of Ceim-
eigenvalues of M
1.000
1.000
-0.500
0.866i
-0.500 + 0.866i
0.168
(fp. 5)
1.000
0
-0.500
0.866i
-0.500 0.8661
when Csim
1.000 + 0.008i
0
0,489
0.860i
-0.510 + 0.869i
when Csim
0.999 - 0.000i
0
-0 -0,955
0.867i
-0.501 + 0.862i
when Csim = 10
1.000 + 0.003
0
-0.497
0.867í
-0.501 + 0.864i
when Csim 30
1.000 + 0.001
0
-0.500
0.8667
-0.500
0.864i
Open Worm simulation
6x6 resolution
Diagram of periodic motion
Figure 6: Left: OpenWorm of images with x resolution for our experiment. Right: Diagram of how the worm motion is viewed as a (uearly) periodic motion.
simulation of a worm motion. Middle: The extracted sequence
First, assume have access to reasonable values for the hyperparameterrs, and show what happens when we use hyperparameters that do not reflect the target system. With such a choice of parameters (see Appendix F.4h, the algorithm outputs an estimate that contradicts to the hyperparemters; with the value Liaxx 25, outputs the estimate 40. In particular, there exist dimensions that output the estimates 8 and 20, from which the final estimate becomes samples Tp since we have no access to the reasonable hyperparameters. On the other hand, we increased the margin P significantly, and then the output becomes 20 < Lmax where each dimension shows 1 20 in this case. In fact, one segment of our video data (recall concatenate the same video to create sequence of indefinite number of images) consists of 120 images and contains 6 periods of sequence.
Note that, this experiment, we use a fixed number of
We mention that the aforementioned fact implies that the choice of hyperparameters may be practically validated by confirming that the outputs are consistent to the parameters.
Next, we assume that the system is lincar and run the DMD over this canonical basis of the state space. Let MDMD be the solution to the exact DMD over the video data, and compute the eigenvalues of Md MD and of the output of Algorithm 2 We tested the algorithm with the fixed hyperparameters given in Appendix F and with varying number of N, namely, 103, 104, and 10 For the cases of 103 and 10a, we only obtained one eigenvalue which is close to 1 + Oi and the others were almost zero. For N = 10a, we obtained three nonzero eigenvalues which are plotted in Figure against the top four eigenvalues of MD The actual nonzero eigenvalues and the estimated errors for all three cases are given in Table 2
From the results, we argue that, for some real applications where the system is not exactly linear, the eigenvalue estimation algorithm may not work well although it does not output insane values.
18

---

Published in Transactions on Machine Learning Research (7/2024)
0.75
DMD
0.50
Estimation
N
Nonzero eigenvalues
Errors
0.25
Im(x)
10a
1.000 0.002:
0.199
0.00
10
1.000 0.002;
0.199
-025
1.001 0.001i
-0550
10a
0.288 + 0.884i
0.172
0.290 + 0.867i
-077
-0.5
0.5
1.0
1.5
2.0
Re(x)
Table 2: Estimated nonzero eigenvalues for N
10ah 10 10", and the total errors to the true DMD matrix M
Figure 7: Estimated eigenvalues having large magni- tudes (red) and the top four DMD eigenvalues (blue).
7 Discussion and conclusion
This work proposed novel algorithms for estimating periodic information about the dynamical systems from bandit feedback contaminated by a sub-Gaussian noise. Since we consider a rather novel problem setup, the sctting itself would be seen as limitation of our work, and we present potentially important list of future works below.
Choice of hyperparameters such as Lmax, N: If those hyperparameters correctly chosen for nearly periodic systems, the outputs of our algorithms are consistent and reasonable across runs, which follows the theoretical insights; therefore, practically, one can check if the hyperparameters are properly chosen by rumning the algorithms. Refer to Section G for related discussions; in short, inappropriate choice of hyperparameters leads to contradicting outputs (e.g., period estimate larger than the assumed maximum value). On the other hand, studying if it is possible to theoretically ensure correctness of hyperparameters (e.g., by standard doubling trick (Cesa-Bianch) et al. 1997 for efficient guessing) identify non-periodic systems is important future work.
Extension to general spectrum information estimation problems: We only impose nearly periodicity on the dynamical systems on top of the linearity for the eigenvalue estimation problem. Nevertheless, additional studics are needed to allow other forms of observations (not limited to bandit feedback) and times irrational numbers. Actually, the
non-periodic systems to consider eigenvalues with arguments asymptotic bounds of the Weyl sum themselves are still valid when it sufficiently well approximated by rational number (Bourgain 1993 Oh). Morcover, allowing control imputs would make cigenvalues of magnitudes smaller than one efficiently recoverable.
Extensions to random dynamical systems: This work studied deterministic dynamical systems; how- ever, we conjecture that, under the condition that the variance of trajectories generated by a random dynam- ical system (RDS) (cf. [Anold (1998)) is sufficiently small, the similar estimation procedure adopted for such RDSs. It is important study if the estimation problem becomes easier when the system driven by particular noise it could be treated
random control input. Also, studying other dynamic structures such the Lyapunov exponents for nonlinear systems is interesting future work.
Study of statistical estimation leveraged by other number theorctical results: The proper use of exponential sums enables us to average out the noise while preserving particular information. Studying when this separation is feasible for different sets of information, noise, and class of problems should be important.
Optimality of the results: Although we gave a sufficient number of samples for provably guarantocing (approximate) correctness of the estimates, it unclear if our sample complexity what one can best achieve under particular problem settings. Recall that the current. problem settings without assumption
19

---

Published in Transactions on Machine Learning Research (7/2024)
boundedness of the set of arms D exclude the lower bound arguments of the minimally required samples as mentioned in Remark 4.4
As such, instead of arguing the tightness, to justify the complexity of our algorithms, we hence mention that the very naive approach for (nearly) period estimation would cost the order of Lmax! sample complexity. To see this, suppose we know the maximum possible (nearly) period Imax then it follows that m a true (nearly) period as a multiple of the fundamental (nearly) period. As such, one could employ the concentration of measures to average out the sample. With sufficiently many sequences of length m depending the could approximately reconstruct the original (noiseless) sequence of length Lmax!
rate of concentration, from which one could estimate a desired L S Luax which is an (aliquot) nearly period.
Lower bound of the minimally required samples may be discussed by using similar arguments to the best arm identification problems (cf. [Kufmaan et al. (2016)); however, our problems consider dynamical systems, and we have no clue on potential technical tools to deal with the arguments at this point.
Acknowledgments
We thank the constructive comments by anonymous reviewers for improving this work. Motoya Ohnishi thanks Sham Kakade, Yoshinobu Kawahara, Emanuel Todorov, Jacob Sacks, Tomoharu Iwata, and Hiroya Nakao for valuable discussions and thanks Sham Kakade for computational supports. This work of Motoya Ohnishi, Isao Ishikawa, and Masahiro Ikeda supported by JST CREST Grant, Number JPMJCR1913, including ATP challenge program, Japan. Also, Moloya. Ohnishi is supported in part by Funai Overseas Fellowship. Isao Ishikawa is supported by JST ACT-X Grant, Number JPMJAX2004, Japan. This work of Yuko Kuroki was supported by Microsoft Research Asia and JST ACT-X JPMJAX200E.
References
Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural informalion processing systems, 24, 2011.
N. Abe and P. M. Long. Associative reinforcement learning using linear probabilistic concepts. In ICML, pp. 3-11, 1999.
J. Adams, N. Hansen, and K. Zhang. Identification of partially observed linear causal models: Graphical conditions for the non non-Gaussian and heterogeneous cases. Advonces in Newral Information Processing Systems, 34, 2021.
C. Acrts, G. Molenberghs, M. Michiclsen, MG. Pedersen, R. Björklund, C. Johnston, JSG. Mombarg, DM. Bowman, B. Buysschaert, PI. Pápics, el al. Forward asteroseismic modeling of stars with convective core from gravity-mode oscillations: parameter estimation and stellar model selection. The Astrophysical Journal Supplement. Series, 237(1):15, 2018.
T. Ahamed, A. C. Costa, and G. J. Stephens. Capturing the continuous complexity of behaviour in Caenorhabditis elegans. Nature Physics, 17(2):275 283, 2021.
R. M. Allen and H. Kanamori. The potential for carthquake early warning in southern California. Science, 300(5620):786-788 2003.
F. J. Auscombe. Sequential medical trials. Journal of the American Statistical Association, 58(302):365 383, 1963.
G. I. Arkhipov, V. N. Chubarikov, and A. A. Karatsuba. Trigonometric Sums in Number Theory and Analysis. De Gruyter, Berlin, New York, 2004.
L. Arnold. Random dynamical systems. Springer-Verlag, 1998.
P. Auer. Using confidence bounds for explotatiion-ecplration trade-offs. Journal of Machine Learning Research, 3:397-422, 2003.
20

---

Published in Transactions on Machine Learning Research (7/2024)
P. Auer, Y. Chen, P. Gajane, C. Lee, H. Luo, R. Ortner, and C. Wei. Achieving optimal dynamic regret for non-stationary bandits without prior information. In Conference on Learning Theory, pp. 159-163. PMLR, 2019.
J. Bakarji, K. Champion, J. N. Kutz, and S. L. Brunton. Discovering governing equations from partial measurements with deep delay autoencoders. arXiv preprint arXiv:2301.05136 2022.
A. Bennett and N. Kallus. Proximal reinforcement learning: Efficient off-policy evaluation in partially observed Markov decision processes. Xiv preprint arXiv:2110.15332, 2021.
O. Besbes, Y. Gur, and A. Zeevi. Stochastic multi-armed-bandit problem with non-stationary rewards. Advances in neural informalion processing systems, 27, 2014.
J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah. Julia: A fresh approach to numerical computing, SIAM review, 59(1):65 98, 2017.
M. A. Bhouri and P. Perdikaris. Gaussian processes meet NeuralODEs: A Bayesian framework for learning the dynamics of partially observed systems from scarce and noisy data. orv preprint or Xrv:2:2003 03385, 2021.
J. Bourgain. Fourier transform restriction phenomena for certain lattice subsets and applications to nonlinear evolution equations. Geometric & Functional Anabysis GAFA, 3(3):209 262, 1993.
S. Bubeck and N. Cesa-Bianchi Regret analysis stochastic and nonstochastic multi-armed bandit problems. Foundations and Trendsl in Machine Learning, 5:1 122, 2012.
H. Cai, Z. Cen, L. Leng, and R. Song. Periodic-GP: Learning periodic world with Gaussian process bandits. Xrxiv preprint ar Xiv: 14422, 2021.
E. J. Candes, J. K. Romberg, and T. Tao. Stable signal recovery from incomplete and inaccurate measure- ments. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 1207)21277-223, 2006.
M. Casdagli, S. Eubank, J. D. Farmer, and J. Gibson. State space reconstruction in the presence of noise. Physica D: Nonlinear Phenomena, 51(1))::52-90 1991.
N. Besa-Bianchi, Y. Freund, D. Haussler, D. P. Helmbold, R. E. Schapire, and M. K. Warmuth. How to use expert advice. Journal of the ACM, 44(3) 1997.
Y. Chen, C. Lee, H. Luo, and C. Wei. A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free. In Conference on Learning Theory, pp. 696-726. PMLR, 2019.
C. Chesneau and Y. J. Bagul. A note on some new bounds for trigonometric functions using infinite products. Malaysian Journal of Mathematical Sciences, 14:273-283 07 2020.
W. Cheung, D. Simchi-Levi, and R. Zhu. Hedging the drift: Learning to optimize under nonstationarity. Management Science, 6896)116961 2022.
J. Conway et al. The game of life. Scientific American, 223(4):4, 1970.
R. Couillet and M. Debbah. Random matria methods for wireless communications. Cambridge University Press, 2011.
S. Curi, F. Berkenkamp, and A. Krause. Efficient model-based reinforcement learning through optimistic policy search and planning. Advances in Neural Information Processing Systems, 14116-114417,, 2020.
V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic lincar optimization under bandit feedback. In 21st Anauaa Conference on Learning Theory, pp. 355-366, 2008.
S. A. Derevyanko, E. Prilepsky, and S. K. Turitsyn. Capacity estimates for optical transmission based on the nonlinear Fourier transform. Nature communications,, 7(1):12710, 2016.
21

---

Published in Transactions on Machine Learning Research (7/2024)
D. L. Donoho. Compressed sensing. IEEE Trans. Information Theory, 52(4):1289-1306 2006.
M. F. Duarte, M. A. Davenport, D. Takhar, J. Laska, Sun, K. Kelly, and Baraniuk. Single-pixel imaging via compressive sampling. IEEE Signal Processing Magazine, 25(2):83 91, 2008.
Y. C. Eldar and G. Kutyniok. Compressed sensing: theory and applications. Cambridge university press, 2012.
C. Furusawa and K. Kaneko. A dynamical-systems view of stem cell biology. Science, 338 217, 2012.
E. Hazan. Introduction to online convex optimization. Poundations and Trends0 in Oplimization, 2(3-4): 157 325, 2016.
E. Hazan, H. Lee, K. Singh, C. Zhang, and Y. Zhang. Spectral filtering for general linear dynamical systems. Advances in Neural Information Processing Systems, 31, 2018.
M. E. Hughes, K. C. Abruzzi, R. Allada, R. Anafi, A. B. Arpat, G. Asher, P. Baldi, C. De Bekker, D. Bell- Pedersen, J. Blau, et al. Guidelines for genome-scale analysis of biological rhythms. Journal of Biological Rhylhms, (2):3880-3990 2017.
S. Kakade, A. Krishnamurthy, K. Lowrey, M. Ohnishi, and W. Sun. Information theoretic regret bounds for online nonlinear control. Advances in Neural Information Processing Systems, 33:15312 13:15312-15325, 2020.
N. M. Katz. Exponential Sums and Differential Equations. (AM-124). Princeton University Press, 1990.
E. Kaulmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-4) 42, 2016.
J. N. Kutz, S. Brunton, B. W. Brunton, and J. L. Proctor. Dynamic mode decomposition: data-driven modeling of complex systems. SIAM, 2016.
S. Lale, K. Azizzadenesheli, B. Hassibi, and A. Anandkumar. Logarithmicc regret bound partially ob- servable lincar dynamical systems. Advances in Neural Information Processing Systems, 33:20876-20888, 2020.
T. Lattimore and C. Szepesvári. Bandil algorilhmss Cambridge University Press, 2020.
A. X. Lee, A. Nagabandi, P. Abbeel, and S. Levine. Stochastic latent actor-critic: Deep reinforcement learning with latent variable model. Advances in Neural Information Processing Systems, 33:741-785 2020.
H. Lee. Improved rates for prediction and identification of partially observed linear dynamical systems. International Conference on Algorithmic Learning Theory, pp. 068-698. PMLR, 2022.
H. Lee and C. Zhang. Robust guarantees for learning an autoregressive filter. In Algorithmic Learning Theory, pp. 490 517. PMLR, 2020.
L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Proc. International Conference on World Wide Web, pp. 661-670, 2010.
L. Ljung. Perspectives on system identification. Annual Reviews in Control, 34(1):1 12, 2010.
H. Luo, C. Wei, A. Agarwal, and J. Langford. Efficiont contextual bandits in non-stationary worlds. Conference on Learning Theory, pp. 1739-1776 PMLR, 2018.
H. Mania, M. I. Jordan, and B. Recht. Active learning for nonlinear system identification with guarantees. Journal of Machine Learning Research, 23(32):1-30, 2022.
K. Menda, J. De B., Gupta, Kroo, M. Kochenderfer, and Z. Manchester. Scalable identification of partially observed systems with certainty-equivalent F.M. Tn ICML, pp. 6830 6840, 2020.
22

---

Published in Transactions on Machine Learning Research (7/2024)
L. Meng and B. Zheng. The optimal perturbation bounds of the Moore-Penront inverse under the Frobenius norm. Linear algebra and ils applications, 432(4):956-99)) 963, 2010.
Z. Mhammedi, D. J. Foster, M. Simchowitz, D. Misra, W. Sun, Krishnamurthy, A. Rakhlin, and Lang- ford. Learning the linear quadratic regulator from nonlinear observations. Advances in Neural Information Processing Systems, 33:14532-14548 2020.
A. Moore, T. Ziclinski, and A. J. Millar. Online period estimation and determination of rhythmicity in circadian data, using the BioDare data infrastructure. In Plant Circudian Nelworks, pp. 13 44. Springer, 2014.
S. Oh, A. M. Appavoo, and S. Gilbert. Periodic bandits and wireless network selection. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), pp. 149:1-1493 149:111 2019.
T. Oh. Note on lower bound of the Weyl sum in Bourgain's NLS paper (GAFA'93).
M. Ohnishi, I. Ishikawa, K. Lowrey, M. Ikeda, S. M. Kakade, and Y. Kawahara. Koopman spectrum nonlinear regulators and efficient online learning. Transactions on Machine Learning Research, 2024.
S. Ouala, D. Nguyen, L. Drumetz, B. Chapron, A. Pascual, F. Collard, L. Gaultier, and R. Fablet. Learning latent dynamics for partially observed chaotic systems. Chaos: An Interdisciplinary Journal of Nonlinear Science, 30, 2020.
E. M. Rathje, N. Abrahamson, and J. D. Bray. Simplified frequency content estimates of earthquake ground motions. Journal of Geotechnécal and Gepeneirommental Engineering. 124(2):150-IL) 159, 1998.
H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5)5527-535, 1952.
Y. Russac, C. Vernade, and O. Cappé. Weighted linear bandits for non-stationary environments. Advances in Neural Information Processing Systems, 32, 2019.
F. Sabetta and A. Pugliese. Estimation of response spectra and simulation of nonstationary earthquake ground motions. Bulletin of the Seismological Sociely of America, 86(2):337 352, 1996.
J.-P. Serre. Linear Representations of Finite Groups. Springer New York, NY, 1977. doi: https://doi.org// 10.1007/978-144684 9458-7.
M. Simchowitz and D. Foster, Naive exploration is optimal for online LQR. In ICML, pp. 8937-8948. PMLR, 2020.
M. Simchowitz, R. Boczar, and B. Recht. Learning linear dynamical systems with semi-parametric least squares. In Conference on Learning Theory, pp. 2714 2802. PMLR, 2019.
P. G. Sokolove and W. N. Bushell. The Chi square periodogram: its utility for analysis of circadian rhythms. Journal of Theoretical Biology, 72(1):131 160, 1978.
Y. Song. A note on the variation of the spectrum of an arbitrary matrix. Linear algebra and its applications, 342(1-3):41-46, 2002.
J. Subramanian, A. Sinha, R. Seraj, and A. Mahajan. Approximate information state for approximate planning and reinforcement learning in partially observed systems. Journal of Machine Learning Research, 23(12):1-88) 83, 2022.
C. Summers, K. Lowrey, A. Rajeswaran, S. Srinivasa, and E. Todorov. Lyceum: An efficient and scalable ecosystem for robot learning. In Learning for Dynamics and Control, pp. 793-803. PMLR, 2020.
B. Szigeti, Gleeson, M. Vella, S. Khayrulin, A. Palyanov, Hokanson, M. Curric, M. Cantarelli, G. Idili, and S. Larson. OpenWorm: an open-science approach modeling Caenorhabditis elegans. Frontiers in Computational Neuroscience, 8:137, 2014.
23

---

Published in Transactions on Machine Learning Research (7/2024)
F. Takens. Detecting strange attractors in turbulence. In Dynamical systems and turbulence, pp. 366-381. Springer, 1981.
S. V. Tenneti and Vaidyanathan. Nested periodic matrices and dictionaries: New signal representations for period estimation. IEEE Transactions on Signal Processing, (114)33736-35500 2015.
F. Trovo, S. Paladino, M. Restelli, and N. Gatti. Sliding-window Thompson sampling for non-stationary settings. Journal of Artificial Intelligence Research, 68:311 364, 2020.
A. Tsiamis and G. J. Pappas. Finite sample analysis of stochastic system identification. In IEEE CDC, pp. 3648 3654, 2019.
A. Tsiamis, N. Matni, and G. Pappas. Sample complexity of Kalman filtering for unknown systems. In Learning for Dynamics and Control, pp. 435-444. PMLR, 2020.
J. H. Tu. Dynamic mode decomposition: Theory and applications. PhD thesis, Princeton University, 2013.
S. K. Turitsyn, J. E. Prilepsky, S. T. Le, S. Wahls, L. L. Frumin, M. Kamalian, and S. A. Derevyanko. Nonlinear Fourier transform for optical data processing and transmission: advances and perspectives. Oplica, 4(3):307-322) 2017.
W. I. T. Uy and B. Peherstorfer. Operator inference of non-Markovian terms for learning reduced models from partially observed state trajectories. Journal of Scientific Computing, 88(3):1-31. 2021.
J. Van De Beek, O. Edfors, M. Sandell, S. K. Wilson, and O. Borjesson. On channel estimation ofdm systems. In IEEE 45th Vehicular Technology Conference. Countdown to the Wireless Twenty-First Century, volume 2, pp. 815-819, 1995.
J. Von Neumann, A. W. Burks, et al. Theory of self-reproducing automata. IEEE Transactions on Neural Networks, 5(1):3 14, 1966.
P. Walters. An introduction to ergodic theory. volume 79. Springer Science & Business Media, 2000.
P. Wedin. Porturbation thoory for pseudo-inverses. BIT Numerical Mathematics, 13()):217-232, 1973.
Н. Weyl. Über die gleichverteilung von zahlen mod eins. Math. Ann.,
1916.
M. O. Williams, I. G. Kevrekidis, and C. W. Rowley. Extending dynamic mode decomposition. Journal of Nonlinear Science, 25:1307-1346, 2015.
approximation of the Koopman operator:
C. Wolfe. On the properties of predominant-period estimators for earthquake early warning. Bulletin of the Seismological Society of America, 9665):1961-1965, 2006.
Q Wu, N. Iyer, and H. Wang. Learning contextual bandits in non-stationary environment. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 495 504, 2018.
T. Zielinski, A. M. Moore, E. Troup, K. J. Halliday, and A. J. Millar. Strengths and limitations of period estimation methods for circadian data. PloS one, 96)4496,, 2014.
24

---

Published in Transactions on Machine Learning Research (7/2024)
A Proof of Proposition 5.2
Proof.
L mmx sup |ael, 1>0
C := VR log(4/6)
D Cn
[ ( lai)
121
Then, VT > 0 satisfies the following inequality
C' C2 + 4(E m)B
C + C + 4(s D
VT max
2(c 11)
2(c p))
if and only if
Liax Sup
4R² log(4/8)
S 28 11
and
T
T
1.2 1 Colu + suppp2 latl)
4R2 log(4/0)
2 al
T
T
Since Tmax 2, D 2 B, P < 7 78PP22 larl: Co(1 + +7) < <3, and
5 #= 0o(1 2)
Lmax
Lmmax
1 / /4Lmax + 1
O0 -1)
2v 2/Tmmxxx
C V C + 4(s BBB C+ C 4(e MDD
max
2(5 -4)
2( 11)
C+ / + 4(E - D
2( 1))
L C
+ D
2
1(E 11)
(e- p)
212 C2
6/2r
5/2 sup:21 [g
< 2/
+
oilE X)2
oolE A)
2T22 C2
9 sup1z1 [0d|
5 1
oblE A)2
oo(E X)
where we used VI-27 27 2yyLmma Since 2: < / V 24100) Lmaxx the statement follows from Lemma
5.1
25

---

Published in Transactions on Machine Learning Research (7/2024)
B Proof of Theorem 5.3
Proof. Let H be the set of all combinations (m, 8, such that m [d], 8 E [Lmax] {0, 10....... .... 1} and {q = a/l: f 1]}.
We remark that
Liax Σ
E- ΣΣ
Liaxx
Σ
Σ
Σ
B(e-1) 1)
A=1 /Steman/ 18
Linax Limax [Lmax
S
d
2
B=1
dT. max log T.max
2
Also, let & be the event such that, for the combination K E K,
[T/0]
4R2 log (Ad12 log Limaxe /8)
Σ
Mo+
[T/33]
[Tp/3]
Because the error sequence satisfies conditionally any subsequence of the filtration {Fr} is again filtration, we obtain, for each E X
using Lemma D.1 and from the fact that
8
Pr [ 21
dL.2 max log Imnx
Define &Tp = -=xxx S
Then, it follows from the Fréchet inequality that
Pr [T = Pr
TTp
2 |8|
- -1-81 - 11)
dT2 max log I Lmmax
LKE
8|.K|
=
2 1 1 8.
d.2 max log Lemax
Let T. be the output of Algorithm 1 We show that, with probability 1- 6, f. (p. vd)-anp of In fact,
suppose İ is not (p, add. We note that < L. There exists E {o..... I 1} and t1.t E Zzo.
1 To (0) fo (0) > p 2Vdu.
um - fo- (42 um)) Put a, = fo+ um. Then, for any t, e Let m' E argmax,, I....d fo+ Tes (8) Tun Eo we have
la: arl 2 aa, - -a,,1- - 24
|| fst P.n (8) fo+ F.ra (0) 2p
Vd
Vd
Thus, by definition, we have
(/f(((r)))) 2
p
p dd
2 dt/
26

---

Published in Transactions on Machine Learning Research (7/202))
Let do =/22 and ç /= /3/ Lmaxx Then, /l(7E) < o L and
8 L R22 log(4/6)
36 5/2 sup:21 |c
05 2)2
ool5 - X)
325- - d max R7t log(4/0)
726-1 1---vVll VdL max supp>1 at
p² r)
A -r) r)
Rt2 (4/(4/)) 72dL2 max
108 max sup ldd
p²(1 r)
p(1
The last inequality follows from < 2/3. Thus, by Proposition 5.2 the algorithm finds B > L in m'-th loop, and the output becomes integer larger than L, which is contradiction.
]
C
Proof of Theorem 5.8
Here, we provide the proof of Theorem 5.8
C.1
Proof
Let
K : (MO...,,N40) C² W,
E.(N) W ((Ea)) Cd Cd.
For linear map M W - W, we define linear maps:
M M2d-1
X(M):
W +
$J M2
Qx(M) = W (())))))))*)) + W.
For 1, we define linear maps on Cd by
A. = X(M)QN (M) ad N K Es(N),
MM = (M)
We note that A,(N;Mp is identical to A,(N) defined in 5.7 We impose the following assumption on (MM)): Assumption 5. The kernel of the linear map ((M) is the same as N(M)).
Note that this assumption holds with probability 1 if we randomly choose ZT.... Fa (see Lemma C.7
The following isomorphicity maintenance lemma provides an explicit description of Bo(N; Mi)t.
Lemma C.1 (Tsomorphicity maintenance lemma). Suppose Assumption holds. Assume N 2 16T.. Let
U1 == I MB)( Cd.
U2 = ( c Cd
Ug = (MM) = W=1 C W.
Leti: U2 + Od be the inclusion map and p: Cdd + UU! the orthogonal projection. Then, restriction of X X(M)) (resp. Mi K) to Us (resp. U²)) induces isomorphism onto Un (resp. Uz). If denote the isomorphism by X (resp, K). Then, (NNNM)) is given by
(N; p² K Mn Q x-1p
27

---

Published in Transactions on Machine Learning Research (7/2024)
Proof. Since we have (M1) (M for all r 2 0 and Assumption 5
surjectivity of K by Proposition
C.5 and bijectivity of QN Uz by Proposition 5.7 we have
U1 = 5 (X
U2 = 12= (M,KK.
Thus, the restriction of (M) (resp. K) to U3 (resp. U22 induces an isomorphism onto U1 (resp. Us). Let us denote the isomorphism by X (resp. K). Then, the last statement follows from Proposition C.4
Lemma C.2. Assumee 2 16L2. Let
A: BI (NM
Then, is independent of N and its eigenvalues are zeros ezcept for (0, d) disditinc eigenvalues of M.
Proof. We use the notation as in Lemma By Lemma
we obtain
B1 (N; Mi) Ba (N; Mi)1 ix M
which is independent of N and its eigenvalues are zeros except for (0, d)-distinct eigenvalues of M.
The following result will be used in the proof of Theorem 5.8 (but essential).
Lemma C.3. We have
| S kvd, (M&2)) & <(d + 1)2d.
Proof. Considering the Jordan normal form, the first inequality is obvious. As for the second inequality, we define J E pdxdd by the nilpotent matrix
1
Then, we have
-- XX(MIlI <
1(T JIlli
(d--))
Σ
= d+ Σ (d- Σ
J=1
= d Σ (d- (d- 5) (111)
j=1
d + (d+ 1)2d
(d 1)d - (d+1)
< (d 1)2d.
28

---

Published in Transactions on Machine Learning Research (7/2024)
Proof of Theorem 5.8 Let A be the matrix introduced in Lemma C.2
Let
(N) V R² log(4de//) /6)
+1
VN
Let M1 and Me1 be matrices as in Corollary 4.3 Then, by Proposition
4.2
we see that
AN M) A.(N, M1) + A. (N, M<1),
(N,, M) BN,, M1) + B, BN, M<1).
We denote by (N; .M) (resp, (NV the low rank approximation via the singular value threshold y(N)
(soe Definition 5.4) By direct computations, we have
| (N; M) (NV:
$ (M) -I [I) Mo(N; +
[I; -I;; -IB [4: (I;; M1) II [B ( [[V)) |IA Bo(N;
[ Mx1 E1 (N) (B)(
By Proposition 5.7 for 0, 1 and for N 2 [2d, 16L2}, we have
< ( MaM QN |
- (L)]
1 Cd (L)
(N: < |X(M<))| ||M ad - (N ||
dRee -a(+ssdd
S [|Xx(=1)]| |||||
NAd-1 d'ee A(N+sd-d)
S Bxvdldd 1)2a
NAd-1
NAd-1
where we used ||| < VdB (Assumption
3 and | s(d+1)22 (Lemma C.3 and v((d+1)d22d
dd46
By Lemma C.1 with Proposition 5.7
that
[|ooNN; M1) KC (O= 1-
By using Lemma D.I and union bounds, we obtain
mxx(|/16(N))rr]1I((\)))) 5(() VN
with probability at least 1 - 8. Assume that
2 (d 1) log( Bx2) + d
Then, we see that [B,(N; M&1) )l < 1/N.. Thus, by Lemma C.6 with probability at least 1 5, we have
|N; (o M1) < ((]) + [N;; Mc1)ll) MI
<8y(N): [N, M, (I= +1)
$ 8 + + Vd)) Cue (L) X 111 (13
Therefore, there exists C > 0 depending on || ||]]],
Ows (L): || ||. || ||, and d such that
R22 (log (1/6) + 1) +1
A MN M) <
N
with probability at least - 8.
29

---

Published in Transactions on Machine Learning Research (7/2024)
C.2 Miscellaneous
We provide expression of Moore-Penrone pseudo inverse:
Proposition C.4. Let A Cm C" be a linear map. Let i: (A) + C be the inclusion map and let p:
CDh D: Then, the Moore-Penrose pseudo incerse A coincides with 1 Ā 1-1
(A)+ be the orthogonal projection. Let Å == AlM(A)) (AA) + If I(A) be isomorphism.
Proof. Let B = p² -.. We remark that A = iAp, i"i = id, pp' id, that ABA A, BAB B, (AB)* = AB, and BA = (BA)". By the uniqueness of Moore-Penross pscudo inverse, B = At
J
Proposition C.5. Let A E Caxd be a matrix and let u E Cd be a vector. Let C Cdd be a linear subspace generaled by { Then, V = I ((Av, A', A?u....,,A. Abr).
Proof. Put = ((Au, It suffices to show that A'v E W for any positive integer j > By the Cayley-Hamilton theorem, A = Σj=1 cAA for some Oj C. Thus, by induction A is a linear combination of A, ......... Ad, namely, N'EW
A)) The inclusion W C V is obvious, we prove the opposite inclusion.
We give several lemmas here.
Lemma C.6 (Perturbation bounds of the Moore-Penrose inverse). Suppose E Caxd a matria. Let E. Cdxd be malria salisfying
1 3C 0, VN E Eso. | S C VN
and let Ag E Adxd be the low rank approrimation of A- E via SVD with the singular value threshold C/VN. Then, we obtain
At 4/ 8C VV +
VN
Proof. Let miin -|Ai1 be the minimal singular value of A. From MMnn & Zheng 2010 (or originally Wedin 1973 and from the fact.
Theorem 1.1)
vdC
|| A A
|
VN
we obtain
At - A///
1 1+ v5
max ||at)|=||[a33 (vā+1) C
[
VN
For N such that 1 N I /o we have
| s SVN/C S 2/Omin- Suppose singular values dk. k E [d].
of A, and ok, & E [d], of A + are sorted in descending order. Then, it holds that
1o ox < |E|
Therefore, for N >
the minimum singular value δu is greater than 0min/2. this case, Åg = A + E, and it follows that A < 2/amin- Hence, for all 2 1, we obtain
2
A
T Umin
30

---

Published in Transactions on Machine Learning Research (7/2024)
from which, it follows that
2C (1 v5) (Vá+1)
8CI|AT|2 (Va+1)
AT A/c
o min
VN
VN
Lemma C.7 (Null space of random matrix). Suppose MR E RRddd k E [d], have the same null space. Then, the null space of
I M1
122 M₂
a Ms
where Ik: & E [d], are unit vectors independently drown from the uniform distribution over the unit hyper- sphere, is the same as those of My with probability one.
Proof. Given any k 1 dimensional linear subspace ((M)) for any & E [d], it holds that the probability that zf_Ms My lies on that space is zero. Therefore, by union bound, and by the fact that the row space is the orthogonal complement of the mull space, obtain the result.
D Azuma-Hoeffdin inequality for exponential sum
Lemma D.1. Let {Xilj=1 for n E Z,o be sub-Gaussion martingale difference with variance prozy R2 and filtration {F₃}. Also, let {az} C be sequence of complex numbers satisfying layl S 1 for all j E [n]. Then, the followings hold, where *|+] stands for Rel-]] or Jm|.].
2R log (2/0)
Pr
aj Xj
2 1 - 6.
4R log (4/5)
Pr
Σ
oj X,
2 1 5.
Proof. For filtration (Filisn we have
axX,]]
E Aore Enj a,x, rorefoa X.11 [n
]] S
x2
E axX,)
E
E
where the first inequality follows from the assumption of filtration, and the second inequality follows from
e Notelan Xal Fn-1] = E [exx [n-1]
2a
E
By induction, we obtain
Aote Ej az xxx;]]
E
e
<
By using Markov incquality and the union bound, follows that
1
n²2
Pr
Re
a
X
<
2e
ZRZ
n
1=1
31

---

Published in Transactions on Machine Learning Research (7/2024)
Similarly, we have
1
12
nu3 2R²
Pr
Jm
a X
> c
<
2c
n
i=1
Therefore, we obtain
16
4R log (4/6)
Pr
Dj Xj
11
11
1
2 log (4/0)
Pr
Σ
Bg
X
n1
n
/=1
Pr
1
Jm
Σ ,jX,
S
2 log (4/6)
π
8
1
12
2
where the first inequality follows from the Fréchet inequality,
E Applications to bandit problems
We briefly cover the applicability of our proposed algorithms to bandit problems (e.g., regret minimization) which is mentioned in the introduction.
A naive approach is an explore-then-commin type algorithm (ef. Robbins 1952); employs our algorithm to estimate nearly period, followed by a certain periodic bandit algorithın such the work in Cai et al. (2021) to obtain an asymptotic order of regret. Caveat here is, because our estimate is only an aliquot nearly period, one may need to take into account the regret caused by this misspecification when running bandit algorithms (e.g., P and μ may lead to (small) linear regret). Avoiding this small linear regret would require the system to be O-nearly periodic and that there exists a sufficiently large gap ensuring p-nearly period with sufficiently small f implies O-nearly period.
Anscombe 1963 One
If one aims at designing an anytime algorithm, the straightforward application of our algorithms may not give near optimal asymptotic rate of expected regret. because the failure probability of periodic structure estimations cannot be adjusted later. To remedy this, one can employ our algorithm repetitively, and gradually increase the span of such procedure. Importantly, samples from separated spans can contributo to the estimate logether when the surplus beyond a multiple of period is properly dealt with. Since failure probability decreases exponentially with respect sample size, we conjecture that increasing the span for bandit algorithm by certain order will lead to the same rate (up to logarithm) of expected regret of the adopted bandit algorithm.
F Simulation setups and results
Throughout, used the following version of Julia Bezanson et al. (007)); for each experiment, the running time was loss than few minutes.
Julia Version 1.6.3
Platform Info:
0S: Linux 148__64-pc-linx-gnu
CPU: Intel (R) Core (TK) 17-6850K CPU 3.60GH
WORD_SIZE: SIZE: 64
LIBM: 1ibopenlibm
32

---

Published in Transactions on Machine Learning Research (7/2024)
Table Hyperparameters used for period estimation LifeGame.
LifeGame hyperparameter
Value
Algorithm hyperparameter
Value
height
12
accuracy for estimation p
0.98
width
12
failure probability bound 5 maximum possible period Imax
0.2
observed dimension
10
observation noise proxy
0.3
ball radius B
v5
Figure The area we focus on for cellular automata experiment.
LLVM: 11bLLVM-11.0.1 (ORCJIT, broadwell) Environment:
JULIA_NUM THREADS = 12
We also used some tools and functionalities of Lyceum Summers al. (2020). The licenses of Julia and Lyceum are [The MIT License; Copyright (c) 2009- 2009-2021: Jeff Bezanson, Stefan Karpinski, Viral B. Shah, and other contributors: https:/ htt///tb.cco//ualiiiiii aigiiaaaannnuiaa/ooniiiii 2019 Colin Summers, The Contributors of Lyceum], respectively.
and [The MIT License; Copyright (c)
In this section, we provide simulation setups, including the details parameter settings.
F.1 Period estimation: LifeGame
The hyperparameters of LifeGame environment and the algorithm are summarized in Table 3 Note μ 0 because it is periodic transition. Here, used 12 x 12 blocks of cells and we focused on the five blocks surrounded by the red rectangle in Figure The transition rule is given by
the cell alive and two or three of its surrounding eight cells are alive, then the cell remains alive.
If the cell is alive and more than three or less than of its surrounding eight cells are alive, then the cell dies.
3. If the cell is dead and exactly three of its surrounding eight cells are alive, then the cell is revived.
F.2 Period estimation: Simple p-nearly periodic system
The dynamical system
Ft Pt 11) + 11 O,41 = =0++ 2m
T+41 11
11
is y-ncarly periodic. See Figure for the illustrations when / 0.2, 5, a = n. is observed that there are five clusters. We mention that this system is not exactly periodic. The hyperparameters of this system and the algorithm summarized in Table
33

---

Published in Transactions on Machine Learning Research (7/2024)
Table Hyperparametens used for μ-nearly periodic system.
System hyperparamettr
Value
Algorithm hyperparameter
Value
dimension
accuracy for estimation p
0.3
μ
0.001
failure probability bound 5
0.2
(x
maximum possible nearly period Imax
8
observation noise proxy
0.3
ball radius
Figure 9: An example of j-nearly periodic system.
F.3 Eigenvalue estimation
We used the matrix M given by
0
0
0
0
0
1 0
0
0
0
M
1
0
0
0
0
0.7
The first 4 x 4 block matrix for permutation. After N steps, it is expected that the last dimension shrinks so that the system becomes nearly periodic. It follows that 4! 24 multiple of the length L. Eigenvalues of 5 are given by 1.000, 1.000, -0.500 0.866i, -0.500 0.866i, 0.168, and the (Bo, 5)-distinct eigenvalues are 1.000, -0.500 0.866i, -0.500 0.866i.
34

---

Published in Transactions on Machine Learning Research (7/2024)
The hyperparameterrs of the environment and the algorithm summarized in Table 5 Note don't necessarily need H, B, and A to run the algorithm as long as the effective sample size is sufficiently large: we used the values (satisfying the conditions) in Table 5 for simplicity.
Table 5: Hyperparametens used for eigenvalue estimation.
Hyperparameter
Value
Hyperparameter
Value
a nearly period L
24
A
failure probability bound observation noise proxy R
0.2
dimension
5
0.3
ball radius B
1
F.4 Realistic simulation
The hyperparancters used for period cstimation that outputs an invalid estimate are summarizod in Table while those for reasonable output are summarized in Table Also, the hyperparameters used for the eigenvalue estimation are summarized in Table g Note for all of them, used the fixed number of sample sizes.
Table 6: Hyperparameters used for worm simulation that outputs incorrect value.
System hyperparameter
Value
Algorithm hyperparameter
Value
dimension
36
accuracy for estimation P
1.0
sample number Tp
3 x 10
maximum possible nearly period Lmax
25
observation noise proxy
Table 7: Hyperparameters used for worm simulation that outputs reasonable value.
System hyperparameter
Value
Algorithm hyperparameter
Value
dimension
accuracy for estimation p
20.0
sample number Tр
x 10
maximum possible nearly period Lmax
25
observation noise proxy R
Table Hyperparameters used eigenvalue estimation worm simulation.
Hyperparameter
Value
Hyperparameter
Value
sample number N
103, 104
103
failure probability bound 5
0.2
dimension
36
observation noise proxy R
1.0
a nearly period L
20
35


Reviews:
[{"review_id": "dc9hiaZh2d", "reviewer": "Reviewer_wo7U", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\nThe paper successfully matches the claims that it makes. It does extend the literature on period estimation and eigenvalue estimation of dynamical system to the sub-Gaussian setting (Theore 4.3 and Theorem 4.8). I like the use of Weyl's sum to establish the guarantees. \n\n**Weakness**\n\nI have some reservations regarding the novelty of the paper. \n\nExtending the Gaussian results to the sub-Gaussian is pretty straightforward. It just requires a simple use of Azuma-Hoeffding inequality and Lemma D.1. Lemma D.1 and its variations have been used across literature. \n\nAlthough the use of Weyl's sum technique is new, the main result follows very simply from the existing bounds on Weyl's sum, e.g., Lemma 4.6.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the following dynamical system:\n$r_t(x_t)= {f^t(\\theta)}^\\top x_t + \\eta_t,$.\nThe goals of the paper are: \n\n1. Estimate the length of the period from the collection of rewards with sample efficiency guarantee.\n2. Estimate eigenvalues of a linear dynamical system with sample efficiency guarantee.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be great if the authors could clearly delineate the technical novelties required to deal with the issues mentioned in the Weakness section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "r1jUwkHydR", "reviewer": "Reviewer_okMR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Main Contributions:\n\nOriginality: This paper introduces a novel use of exponential sums to create asymptotic bounds of dynamical structure, i.e. period and spectrum of dynamic system. This mathematical machinery has not yet been applied to problems within the statistical learning framework, and this connection alone is a compelling research perspective. \n\nSignificance: The authors establish a litany of results, under the more loose assumptions of sub-Gaussian noise and with no claims of autonomy and observability, extending the previous dynamical systems literature into problems of bandit feedback.\n\nMain Weaknesses:\nMotivation: Although the mathematical complexity behind Weyl sums makes them a compelling topic of study, the motivation to use them within this context is lacking within the paper. An introduction to the related work about these sums as well as a section giving a brief introduction to their properties of note would be beneficial. In addition, motivation for studying the intersection of the two challenges faced in the work, dynamical system identification and bandit feedback would be beneficial. \n\nExperiments/Algorithms :  The algorithms are novel, yet a discussion of the benefits and weaknesses and comparison to others in the literature is scarce.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on extracting structure from dynamical estimation problems with bandit feedback by use of exponential (Weyl) sums. These sums elicit spectral and periodic information about the system and allow for estimation of these quantities.  The authors then propose tractable and efficient algorithms for computing these quantities of interest, giving sample complexities and convergence results, and conclude with experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Examples: It would be nice to have a few examples explaining how the bandit feedback interacts with the linear dynamical system estimation.\n\nQuestions:\nIs the framework of bandit feedback necessary for the results generated? Could we instead just assume that x_t is a parameter on which the reward hinges?\nThere are a few minor grammatical typos, e.g. Assumption 3.2 family should be families etc.", "broader_impact_concerns": "N/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eFFfmueG4s", "reviewer": "Reviewer_nJrm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "On top of some of the strengths mentioned in the \"Summary of Contributions\":\n1. Both Period/Eigenvalue estimation results are associated with non-asymptotic bounds. The proof logic and the introduction of notations and definitions are also smoothly presented. \n2. The use of exponential sum, particularly Weyl sum, is likely of independent interest and connects practical applications and well-known analytical number theory results. Proposition 4.7 simultaneously ensures the protection of eigenvalue information and the cancellation of noises. \n3. The experimental results look good as the algorithm achieved zero error on Period Estimation and near-zero error on Eigenvalue estimation. Note that the period value is an integer, so zero error may be expected for other algorithms. However, eigenvalues are Real values, and algorithms are unlikely to achieve zero error in general settings.\n\nWeaknesses:\n1. The Related Work and Introduction sections introduce many relevant works and seem redundant, especially since the paper does not dive deep into any research closely related to its own.\n2. Theorems 4.3 and 4.8 present some sample/observation size bounds for the underlying problems but do not justify their optimality. While the authors mentioned that this could be some future research direction, it is a common scenario where the difficulty of a statistical estimation problem decreases significantly for sufficiently large samples. For this very reason, researchers often aim to determine the min-max sample complexities or regrets. I suggest the authors consider providing some justifications for the quality and goodness of their results. Similarly, it's unclear how to choose the parameters for practical applications.\n3. The introduction motivates the problem through many vital applications in control, economics, statistical machine learning, and biological/earthquake/chemical/asteroseismic analysis. However, the experiment section presents only a toy example with a period 8. This seems to be a significant discrepancy. Therefore, I would suggest the authors conduct some experiments on real-world data to close this gap.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem of estimating periodic information, such as (effective) period and selected subset of eigenvalues, about dynamical systems from bandit feedback under sub-Gaussian noises. \n\nThe primary technique leverages some analytical results on exponential sums, which reduce noises while retaining sufficient information about the underlying system. For a sufficiently large sample and properly chosen parameters (and some additional assumptions about the system), the results are two-fold: 1) One can estimate the (effective) period of the denoised output sequence; 2) For a linear system, one can further approximately recover some of the eigenvalues. \n\nThe paper complements the theoretical claims and theorems with a toy experiment/example from the famous LifeGame of Conway. With properly chosen parameters, the synthetic results are broadly consistent and accurate.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the Weaknesses subsection under \"Strengths and Weaknesses.\" Specifically, I would suggest the authors to:\n1. Reduce the redundancy in the Introduction and Related Work, and, if possible, discuss how the techniques and results differ from the closest research work(s).\n2. Justify the quality and goodness of the results and guide parameter selection in practical applications (with reasonable justification). \n3. Conduct some experiments on real-world data to mitigate the discrepancy between problem-motivating applications and the experiments in the paper.", "broader_impact_concerns": "The submission is mainly theoretical in the current format, demonstrating its application via a toy problem. I do not have immediate concerns about the ethical implications of the work that would require adding a \"Broader Impact Statement.\"", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers found that the results in this paper follow immediately from existing works. However, novelty is not a criteria in TMLR, so I will argue that there is an audience for this paper.

I suggest authors to go over the reviews carefully and make modifications that would address their concerns as much as possible.
Decision: Accept (poster)