TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning
Authors: Konstantin Sozykin
Andrei Chertkov
Roman Schutski
ANH-HUY PHAN
Andrzej Cichocki
Ivan Oseledets
Venue: NeurIPS 2022 Accept (2022)
Keywords: Black-box
Optimization
Reinforcement Learning
Tensor Train
Cross approximation
Maximum Volume
Quantized networks

Abstract: We present a novel procedure for optimization based on the combination of efficient quantized tensor train representation and a generalized maximum matrix volume principle.
We demonstrate the applicability of the new Tensor Train Optimizer (TTOpt) method for various tasks, ranging from minimization of multidimensional functions to reinforcement learning.
Our algorithm compares favorably to popular gradient-free methods and outperforms them by the number of function evaluations or execution time, often by a significant margin.

TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning
Konstantin Sozykin
Andrei Chertkov
Roman Schutski
Anh-Huy Phan
Andrzej Cichocki
1
Ivan Oseledets
Abstract
We present novel procedure for optimization based on the combination of efficient quantized tensor train representation and generalized maximum matrix volume principle. We demonstrate the applicability of new Tensor Train Optimizer (TTOpt) method for various tasks, ranging from minimization of multidimensional functions to reinforcement learning. Our algorithm compares favorably to popular gradient-free frree methods and outperforms them by the number of function evaluations or exccution time, often by a significant margin.
Introduction
In recent years Icarning-baste baannd algorithms achieved impressive results in various applications, ranging from image and text analysis and generation [52] to sequential decision making and control [40]
and even quantum physics simulations [49]. The vital part of every learning- based algorithm is
an optimization procedure, e.g., Stochastic Gradient Descent. In many situations, however, the problem-specific target function is not differentiable, too complex, or its gradients are not helpful due the non-convex nature of the problem (30 2 (8)) The examples include hyper-parameter selection during the training of neural models, policy optimization in reinforcement learning (RL), training neural networks with discrete (quantized) weights [57] or with non-differentiable loss functions [20]. In all these contexts, efficient direct gradient-free optimization procedures are highly needed.
Recently, [53] showed that essential class of gradient-free methods, namely the evolutionary strategies (ES) 22 26), are competitive in reinforcement learning problems. In RL, the goal is to find the agent's action distribution (the policy), maximizing some cumulative reward function J. The policy is usually parameterized with a set parameters 0. It follows that the reward is a function of the parameters of the policy: (O)) J(O). The idea of (53) and similar works [36] [5 10
J(O,, 02.... 0a) with respect to the parameters of the policy. We pursued similar approach to transform traditional Markov
is to directly optimize the cumulative reward function J(O)
Decision Process into an optimization problem (we provide the details in Appendix B.3). Although
the agents trained with ES often demonstrate more rich behavior and better generalization compared to traditional gradient-basse policy optimization, the convergence of ES is often slow [[]
Equual Contribution, corresponding emails (konstantin.sozy) wozzkkn..accerrteeee @skoltech.ru
1 "Center of Artificial Intelligence Technology, Skolkovo Institute of Science and Technology (Skoltech)
Moscow, Russia
RRIKEN Center for Advanced Intelligence Project (AIP), Tokyo, Japan
$ Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland
Artificial Intelligence Research Institute (AIRI), Moscow. Russia
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

As an alternative to previous works, we present tensor tensor-based gradient-free free optimization approach and apply it advanced continuous control RL benchmarks. The proposed algorithm. Tensor-Train (TT) Optimizer (TTOpt). works for multivariable functions with discrete parameters by reformulating the optimization problem in terms of tensor networks. Consider a function J(0) Na + R of d-dimensional argument 0, where each entry 0g of the vector A takes a value in the discrete set {wi)?= The function may be viewed as an implicitly defined d-dimensional tensor J. Each entry in J is value of J for some argument. Maximizing J is equivalent to finding the sets of indices (0 J M of maximal entries (jmas m= of J.
By using only a tiny fraction of adaptively selected tensor elements (e.g., a small number of function evaluations), our method builds representation of J in the TT-format and finds set of the largest elements. Although the algorithm works only with functions of discrete arguments, the grid size for each parameter can be huge thanks to the efficiency of the TT-format. Fine discretization makes possible to almost reach a continuous limit and obtain large precision with TTOpt. The strength of our approach is, however, the direct handling of discrete (quantized) parameters.
Contributions. We propose an efficient gradient-free optimization algorithm for multivariable functions based on the low-rank TT-frrmat and the generalized maximum matrix volume principle" We demonstrate that our approach is competitive with a set of popular gradient-free methods for optimizing benchmark funetions and neural network- agents in RL problems. We empirically show that agents with discrete (heavily quantized) weights perform well in continuous control tasks. Our algorithm can directly train quantized neural networks, producing policies suitable for low-power devices.
Optimization with tensor train
In this section, we introduce a novel optimization algorithm. We show how represent the optimiza- tion problems in the discrete domain efficiently and then formulate optimization as a sampling of the objective function guided by the maximum volume principle.
2.1 Discrete formulation of optimization problems
We first need transfer the problem to the discrete domain to apply our method. It may seem that discretizing an optimization problem will make it harder. However, it will allow us to use powerful techniques for tensor network representation to motivate the algorithm. For each continuous parameter
0g (k- = 1.2..... d) of the objective function J(0) we introduce a grid {0( Nv 1n At each point (o(m)) 0g ml22) (lma)) of this grid with index (m1, 72,..... na)) the objective function takes a value (( (0()) (((aa) J[n1, .2..... na]]- We thus can regard the objective function an implicit d-dimensional tensor I with sizes of the modes N1, ,,,....,NV NN. Finding the maximum of the function (()) translates into finding the maximal element of the tensor J in the discrete setting.
........)
Notice that the number of elements of J equals: [ = Ni -N- ..... Na (maxigksa N
The size of J is exponential in the number of dimensions d. This tensor cannot be evaluated or stored for sufficiently large d. Fortunately, efficient approximations were developed to work with multidimensional arrays in recent years. Notable formats include Tensor Train (TT) 47 46 50
44 63], Tensor Chain/Tensee Ring (29 66 and Hierarchical Tucker 21). We use the most studied
TT-format [3] but the extensions of our method to other tensor decompositions are possible.
By tensors mean multidimensional arrays with number of dimensions d (d 2 1). A two-dimensional tensor (d 2) a matrix, and when 1 is a vector. For scalars we use normal font, we denote vectors with bold letters and we use upper case calligraphic letters (A, B, .....) for tensors with d > 2. Curly braces define sets. We highlight discrete and continuous scalar functions of multidimennsioall argument in the appropriate font, e.g.. J(). in this case, the maximum and minimum values of the function denoted by Jmus and Jmnn. respectively.
We implemented the proposed algorithm within the framework of the publicly available software product: https://github. www htt.hhhwww.ccoeeeeeeeeeeeeoere/e

---

2.2 Tensor Train decomposition
Definition 2.1. tensor E R Ni X is said be in the TT-format 46 its elements are represented by the following expression
Ra
R₁
Ra
I [m1, 122 . .d) =
Σ
Σ
na, (1)
r==1
where nig 1....... Nº for h: .,..
TT-format the d-dimensional tensor J is approximated as a product of three-dimensional tensors Gs E R R2-1 XNN XRe, called TT-cores. The sizes of the internal indices Ry, R1. Ra (with convention Rs = Ra = 1) are known as raranss. These ranks control the accuracy of the approximation.
The storage of the TT-cores, 92........ Ga. requires at most d maxisksa N₂ (maxosk<d R memory cells, and hence the TT-approximation is free from the curse of dimensionality" if the TT-ranks are bounded. The basic linear algebra operations (such finding norm, differentiation. integration, and others) can also be implemented in the TT-format with polynomial complexity in dimensionality and mode size.
Building I'Taaproxiimation Several efficient schemes were proposed to find TT-approximation if all or some of the elements of the initial tensor known or may be generated by the function's 's call. Examples include TT-SVD 47 46). TT-ALS 27 and TT-CAM 48 (Cross Approximation Method
the TT-format).
We build upon the TT-CAM but modify not to compute the approximation for the entire tensor, but rather to find small subset its maximal entries. The original algorithm builds a TT-approximation by adaptively requesting elements of the imput tensor. As we will show below, these elements with high probability will have large absolute values. Based on this observation, we formulate robust optimization algorithm for multivariate functions (either discrete or continuous). To simplify the understanding, we outline the approach for the wwo-dimensional case, and after that, we describe our gradient-free optimization method for the multidimensional case.
2.3 Maximal element in matrix
The Cross Approximation Method (CAM) for matrices [8] g |I well-established algorithm for building rank-R approximation J of an implicitly given matrix J:
J J J, j= Jn.
where Jo consists of R columns J, JR is composed of rows of J, and a submatrix at their intersection. Such approximation (also called cross skeleton dccomposition) may be built iteratively using a well known alternating directions method and a maximum volume (maxvol) will sketch below.
algorithm" [8]
Intuition behind TTOpt. The main interest optimization problems is not the approximation itself, but the following property of the resulting maximum volume submatrix J. [18] proved that j is an R x R submatrix of maximal volume (in selected rows and columns) then the maximal (by modulus) element Jmaz E bounds the absolute maximal element Jmaz in the full matrix J:
Jmaz R2 2 Jman-
'The number of elements of an uncompressed tensor (hence, the memory required to store it) and the number of elementary operations required to perform computations with such tensor grow exponentially in dimensionality. This problem is called the curse of dimensionality.
"The maxvol algorithm finds R rows an arbitrary non-degenerate matrix A E N (N > R) which span mexiiall-volume R x R submatrix Å. The matrix À has maximal value of the modulus of determinant on the set of all nondegenerate square submatrices of the size Rx R. We describe the implementation of maxvol in Appendix A.1. The algorithm greedily rearranges rows of A to maximize submatrix volume. Its computational complexity O(N Rt KN KNR), where K is number of iterations.

---

No. Ny. M... N2
.140
J/
Compute J(6)
Search for Jaan
5
Search dain
1:0.9
10
J,
o..
.N.
seroapo
46-1
.
Je-1
Re.a"
N4-1
Re-4
100
J
261
The scheme of the cross approximation algorithm for matrices using the alternating direc- tion and maximal-volume principle. Green bars represent generated rows/columns; purple hars rows/columns selected for generation in the next step by the maxvol algorithm. The method allows to find the optimum of the two dimensional func- tion J(1,, 02).
Figure 1:
Figure Conceptual scheme of TTOpt al- gorithm based the alternating direction and maximal- volume approaches for tensors. Only small part of the tensor is explicitly generated during this procedure, as shown here with green columns. For the simplicity of presentation, the rows and columns se- lected iterations drawn continuous blocks (they are not in practice).
This statement is evident for R = 1. and for the case R >> it gives an upper bound for the element. By using elementwise transformations of J, this upper bound can used to obtain sequence that converges to the global optimum. The main idea of the maxvol-based methods is that it is easier to find a submatrix with large volume rather than the element with the largest absolute value. Moreover, our numerical experiments show that this bound is pessimistic, and in practice, the maximal-volume submatrix contains the element which is very close to the optimal one.
TTOpt algorithm for matrices. The idea of the TTOpt algorithm for matrices is to iteratively search for the maximal volume submatrices in the column and row space of the implicitly giver innput matrix J E RRN N.Nx, After T iterations series of "intersection" matrices {f(0)T E R R is produced. The maximal clement is searched in these small submatrices. We schematically represent the TTOpt algorithm in Figure and a description is given below:
1. At the initial stage, we set the expected rank of the approximation, H. and select A ran- dom columns ((C,1), We then generate the corresponding column submatrix J J[: [(C.)] E NR, Using the maxvol algorithm, find the maximal-volume submatrix j()) E IR RxR in J( and store its row indices in the list (R.1).
2. The indices ((R.1) used to generate row submatrix J( (T E RRXNs Then, using the maxvol algorithm, we find the maximal-volume submatrix j(2) in the matrix n and store the corresponding column indices in the list (C,,2)
'The matrix is specified function J(-) that allows calculate the value of arbitrary requested element (n1, R2), where < nu < maximum modulus element of such matrix. The method of finding the minimal or maximal elements within the framework of this algorithm will be described in Section 2.6
< na N2. We present the approach approximate the value of the

---

3. We generate the related columns JC J[: RC22), apply again the maxvol algorithm to the column submatrix, and iterate the process until convergence.
4. The approximate value of the maximum modulus element of the matrix J is found as
Imax = max max (J()), max (J(2)),.... max (J()).
(4)
2.4 Optimization in the multidimensional case
As explained previously, the target tensor, is defined implicitl, e.g., by a multivariable function We propose a novel method to find the optimum in this implicit tensor. We outline the approach below and provide detailed algorithms in Appendix A.2.
As shown in Figure 2 we begin by considering the first unfolding
E NN. of the tensor I and select R1 random columns ,10), Precisely, (() here is list of Rt random multi-indices of size - 1, which specify positions along modes k = 2 to k = We then generate submatrix 5 E x for all positions along the first mode (shown in green in Figure 2 Like in matrix
case, apply the maxvol algorithm find the maximal-volume submatrix J1 E R R and store the corresponding indices of Rt rows the list 1(8)
In contrast with matrix case, we cannot generate the row submatrix J(Th) E RR XNyNa... for the selected row indices 1(²), since contains an exponential number of elements. The following trick is used instead. We consider the implicit matrix J{At and reshape it to a new matrix J2 E R R. Na...Na We sample R2 random columns T in the matrix J2 and generate the entire small submatrix J[(C) E N2x Next we find the maximal-volume submatrix J2 TR Rax (C) and store the corresponding R2 row multi-indices in the list (()) The resulting submatrix J (R)) R Ne.. is then transformed (without explicitly evaluating its elements) into the matrix J3 E RRRNNN
We continue the described operations, called sweeps, until the last mode of the initial tensor, J, is reached. After that, we repeat the process in the opposite direction, sampling now the row indices instead of the column indices. These sequences of forward and backward sweeps are continued until the algorithm converges to some row and column indices for all unfolding matrices or until the user-specified limit the number of requests to the objective function, J, exceeded. Finally, after T sweeps, the approximate value of the maximum modulo element can be found by the formula { as in the wwo-dimensional case.
Note that currently there no analog of Eq. L in the multidimensional case, and hence there are formal guarantees of the convergence of the sweeps to the global minimum, nor the rate of this convergence. The only guarantee is that the result will monotonically improve with iterations.
2.5 Complexity of the algorithm
can be easily shown that the described algorithm requires O (d- maxisked RN) elements of the implicit tensor in one sweep. Thus, with total number of sweeps T. will have
evaluate only
o T..d O max (N&
(S)
ISkSd
calls to the objective function J. practice, it turns out to more convenient to limit the maximum number of function calls, M, according to the computational budget.
'The k-th unfolding Js the d-dimensional tensor J C N is matrix Js My x N441...N4 with elements JR Ri, T4g, m1t+,...., Thg J[n,, o2,..., for all indices.
"The TTaapproximation [ of the tensor I may be recovered from the generated columns ((C) and maximal- volume submatrices Ju (k = ........d as follows: G. = J J E R Ra-1 N. xR, where G. is the 2-th unfolding of the k-th TT-core. However, we do not consider this point in more detail, since in our work, the main task is to find the minimum maximum value of the tensor, to construct its low-rank approximation.
5

---

If the time of a single call to J is significant, then the effort spent on the algorithm's operation will be negligible. Otherwise, the bottleneck will be the calculation of the maximal-volume submatrices by the maxvol algorithm. Taking into account the estimate of the maxvol complexity, given in Appendix 1, it can be shown that in this case the complexity of our algorithm is
O
T.T. ..d. max (Na Isked
(6)
2.6 Implementation details
For the effective implementation of the TTOpt algorithm, the following important points should be taken into account (see also the detailed pseudocode in Appendix A.2).
Stability. Submatrices _ (or J and JR. for the -vo-dimensional case) that arise during the iterations may degenerate, and in this case it is impossible to apply the maxvol algorithm. To solve this problem, we first calculate the QR decomposition for these matrices and then apply the maxvol to the corresponding Q factor
Rank selection. We do not know in advance the exact ranks R1, R2..... Rg of the unfolding matrices (or rank the matrix for the two-dimensional case). Therefore, instead the maxvol algorithm,
its modification, i.e., the rect maxvol algorithm [39] within the framework of which several (" ("most important") rows are added to the maximal- volume submatrix. this case, have j(() E [R R. _ E ( etc. Note that the final approximation obtained in this case may have an overestimated rank, which, if necessary, can be reduced by appropriate rounding, for example, by truncated SVD decomposition.
Mapping function. Maximal-volune submatrices contain the maximum modulus element but not the minimum maximum element of the tensor (i.e., the sign is not taken into account). We introduce dynamic mapping function to find the global minimum (or maximum). Instead of at each step of the algorithm, evaluate [0
g(æ)
π
atan (J(xz) - Jmin),
2
where Jmin is the current best approximation for the minimum element of the tensor.
Quantization. To reach high accuracy, we often need fine grids. In the case when the sizes of the tensor modes N1, N2,.... . Na are large, the sizes of unfolding matrices become large, which leads to a significant increase computational complexity of the maxvol algorithm. To solve this problem, we apply additional compression based on quantization of the tensor modes [45) Assume without the (k: 1,2,....
P 2; 2). Then we loss of generality that the size of each mode is N₂ x..xxxxxxxxxx0 Xa into the tensor J Pxxxx...x.
can reshape the original d-dimensional tensor I E RR..xNN, of higher dimension d' g, but with smaller modes of size P. The TTOpt algorithm can be applied for this "long" tensor instead of the original ond n1| We found that this idea significantly boosts the accuracy of our algorithm and reduces the complexity and execution time. Typically, P is taken as small as possible, e.g., P=
Experiments
To demonstrate the advantage of the proposed optimization method, tested TTOpt several numerical problems. First, we consider analytical benchmark functions and then the practically
'It can be shown that this operation does not increase the complexity estimate 6 of the algorithm. 'The rect maxvol algorithm allows find R AR in arbitrary nondegenerate matrix A R (N > N + AR) which an approximation to rectangular maximal-volume submatrix of given matrix A. Details about rect_ maecollaalllllllo are provided in Appendix A.I.
'hee mapping function should be continuous, smooth, and strictly monotone. There various ways
choose such function. However, during runs, turned out that the proposed function (7) most suitable.
If the maximal rank R > P. we select all indices for first & modes until p& > R. We note however that this detail does not change the global behavior of the TTOpt algorithm.

---

Table 1: Comparison of the TTOpt optimizer versus baselines in terms of the final error (absolute deviation of the obtained optimal value relative to the global minimum) and computation time 7 (in seconds) for various benchmark functions. See Table 1 in Appendix B.1 with the list of functions and their properties. The reported values are averaged over 10 independent runs. The upper half of the table presents gradient free (zeroth order) methods, and the lower half is for first and second order methods.
F7
F2
FJ
F4
F3
P6
F7
A8
A9
F10
TTOPT
3.9E-06
1.9E-07
1.38-12
4.46-15
2.86-02
1.15-01
5.56-09
4,65-11
1,35-01
1.3E-44
2:45
2.52
GA
9:76-02
8.40-03
5.80-03
2.06-400
3.9r-64
1.04401
1:35:01
7.96-01
6.20-03
4.24+03
6.21
4.55
5.09
4.47
5.85
5.69
5,05
5.04
5.04
4,70
OPENES
1.85-01
1,76.02
1,25.03
9,76400
3.86-00
2.14000
4.28-03
2.62
1:08
1.52
1.08
2.41
2,01
1.39
1.39
1.62
1.12
CM
5.186287
3:16.01
9,3u-77
2.00:400
7.694289
1.98401
5.56.02
9.36401
2.9
1.2
10.
17.15
DE
c
1,18400
38.97
4.3g-02
38.06
3.38
$1.05
9:06-05
39.48
1.5E 01
41.35
1.66-01
+1.40
2.06:01
+1.34
6.26+00
41.31
6.6E-01
37.97
3.86+02
38.64
NB
1.58401
6.5r-000
3.90401
1.25-01
2:40:0
6.6r:00
1.6r+10
6.3r401
3,4m:400
5.21.403
45.23
46,08
37.50
45.91
48.07
37.16
40.95
44.95
44.05
46.9/
PSO
1.38101
5.38-00
3.56+01
9.
2.06+01
2.55-01
2.0
2.38401
5.1E/01
2.9g402
17.19
17.01
65.50
13.39
46.80
61.97
16.80
12.78
63.15
17.13
BFGS
1,94401
1.1e-00
199401
4.36-13
1.26 02
6,46+00
2,46:05
7.06+01
4.26+00
2.1e+02
0:11
002
003
0.00
0.1
0.04
0.01
L-BFGS
1.95401
1,94000
4.06-10
4.36-13
1.25-02
4.5g+00
4.5 4.50-10
7.08-01
4. 260000
2.14403
0:01
0.05
0.05
0.60
0.01
0.02
0.02
0.01
0.61
0.0r
0G
1,94401
004
N7A
0.00:400
2.06-022
4,40:000
2.96-12
7.0c+01
4.20=000
2.14:403
0.00
0.07
N/A
0.60
0.01
0.88
0.02
0.01
0.83
0.00
NCG
1,98401
3.46-00
1,78-19
0,08+00
7.46-02
6,46400
2.16:12
1.06-01
4.26-000
2,26+00
NEWTON
1.98401
2.20-00
1.14411
0.08:400
3.21-02
6.4m400
2.8a-24
7.00-01
4.20-000
2.18403
0:01
0.02
0.91
0.00
0.01
0.10
0.01
0.01
0.01
0.00
NCG
1.95401
2.4p-10
4.0n-12
4.50000
4.45-00
1,25-14
7.0r-01
2r-00
2.18401
0.01
0.12
0.01
0.00
0.02
0.03
0.01
0.00
0.62
0,01
TR
1.98401
7.00+000
3.26-13 13
4.0u-12
6.1n.41
1.60:400
5.3t-11
7.0ue011
4 4.20+00
2.1
12.97
significant problem of optimizing the parameters of the RL agent. We select GA (Genetic Algo-
rithm 226 60), openES (basic version of OpenAl Evolution Strategies (53) and cmaES (the
Covariance Matrix Adaptation Evolution Strategy (22) as baselines for both experiments. Addi-
tionally we used DE (Differential Evolution (59] ), NB (NoisyBandit method from Nevergrad (5)
and PSO (Particle Swarm Optimization 224 33 for benchmark function We also compared
the proposed approach with cuddient-based methods applied for all benchmark functions 13 BFGS Seoydenn-letcher-Golffee
algorithm), L-BFGS (Limited-memory BFGS), CG (Conju- gate Gradient algorithm), NCG (Newton CG algorithm), Newton (Newton Exact algorithm), TR NCG (Trust-Regiod NCG algorithm) and TR (Trust-Region Exact algorithm).
According to our approach, the TTOpt solver has the following configurable parameters: a and b are lower and upper grid bounds (for simplicity, we use the same value for all dimensions); R is a rank (for simplicity, we use the same value for all unfolding matrices); P is submode size (mode size of the quantized tensor; for simplicity, we use the same value for all dimensions); q is the number of submodes in the quantized tensor (each mode of the original tensor has size N P9); M is a limit on the number of requests to the objective function.
3.1 Benchmark functions minimization
To analyze the effectiveness of the TTOpt, we applied it to 10-dimensional benchmark functions with known global minimums; see Table in Appendix B.1 with the list of functions and their properties (note that some of the considered benchmarks are multimodal non-separable functions). Also, in Appendix B. we present a more detailed study of the TTOpt solver and the dependence of the accuracy on the value of its parameters (R, q and M).
We used implementations of the methods from available packages estool hhttps://github... com/ hardmaru/estool] pycma (https://github.cm com CMA EEStA-ES/yycee ES/pycma and nevergrad (https://github com/
"We used implementations from the package https: //gtttu www./ofeima.......mmmmmmmmaiaaae http://eeemmm//ttooor--aaaiaiiie We carried out computations with all methods from this library. except for Trust sust-Reeionn GLTR (Krylov) and Dogleg methods, for which the calculation ended with error for most benchmarks.
7

---

Table 2: The result of the TTOpt optimizer terms of the final error (absolute deviation of the obtained optimal value relative to the global minimum) and computation time (in seconds) for benchmark F/ (Ackley function) for various dimension numbers.
DIMENSION
d
= 50
100
500
ERROR,
3.9E-06
3.9E-06
3.9E-06
3.9E-06
TIME. 3.1
40.1
143.9
3385.3
Table 3: Mean E and standard deviation of the final cumulative reward. The environments encoded using capital letters Swimmer-v3, Lunarl LanderContinnouus-22 InvertedPendulum-Ve and HalfCheetah-v3. The left sub-table is for mode size N 3, another is for mode size N = 2 Results are averaged over 10 random seeds.
S(3)
L(3)
I(3)
H(3)
S(2*)
L(2")
I(2")
H(22)
357.50
290.29
1000.00
4211.02
311.82
286.87
1000.00
2935.90
TTOPT
6.59
24.40
0.00
211.94
29.61
21.65
0.00
544.11
349.91
283.05
893,00
2495.37
359.79
213.75
222.86
3085.80
GA
10.04
16.28
283.10
185.11
4.21
99.67
342.79
842.76
342.31
214.55
721.00
2549.83
340.54
221.95
621.00
2879.46
CMAES
36.07
93.79
335.37
501.08
78.90
133.80
472.81
929.55
E
318.39
114.97
651.86
2423.16
109.39
73.08
224.71
1691.22
OPENES
44.61
113.48
436.37
602.43
40.11
163.33
217.51
976.96
In all experiments with baselines (GA, openES, cmaES, DE, NB, PSO, BFGS, L-BFGS, CG, NCG, Newton, TR NCG and TR), we used default parameter values. In Appendix B.2 we also present the additional experiments with Bayesian Optimization [37]. For TTOpt selected rank R = 4, submode size P = 2 and the number of submodes = 25. For all methods, a limit on the number of requests the objective function is chosen M 10 All calculations are performed on a standard laptop.
The results are demonstrated in Table I For each method we list the absolute deviation of the result Jmin from the global minimum Jmin i.e., e | Jmin J. We also present the total running time, Compared to other benchmarks, TTOpt is consistently fast, accurate and avoids random failures to converge seen in other algorithms. Additionally, TTOpt turns out one of the fastest gradient-free free algorithms (GA, openES, cmaES, DE, NB, PSO), despite a simple Python implementation.
One of the advantages of the proposed TTOpt approach is the possibility of its application to essentially multidimensional functions. Table 2 we present the result of TTOpt for the F/ benchmark function of various dimensionality (results for other benchmarks are in Appendix B.1). Note that as limit on the number of requests to the objective function we chose AM 10 d, and the values of the remaining parameters were chosen the same as above. As can be seen, even for 500-dimensional functions, the TTOpt method gives a fairly accurate result.
3.2 Application of TTOpt to Reinforcement Learning
We used several continuous RL tasks implemented in Mujoco 61 and OpenAI-GYM 8 Swimmer- v3 [6], ummarlanderrComiiuuuu--
InvertedPenddulum-V and HalfCheetah-v3 (44. all experi-
ments, the policy is represented by a neural network with three hidden layers and with tanh and ReLU activations. Each layer is a convolution layer. See additional details about hyperparameters in Table 6 in Appendix B.
We discretize (quantize) the values of agent's weights. The TTOpt method used to optimize discrete agent's 's weights in order to maximize the cumulative reward of the episode. This corresponds to on-policy learning.
"'ee chose rank R using the following heuristic. The minimal number of sweeps fixed T follows that the algorithm will need 2 T (dq) P. R² function calls. With given limit the number of function
requests M, the rank can be estimated as R S v IT
18

---

HalfCheetah-vd
HalfCheetah
averass rewards 10P
50
average rewerdss
Toy:
TTo cnaE5
openE5
spanES
target roward
targt roward
2500
5000
10000
12500
15000
Number of function queries 10*
seconds
Figure 3: Training curves of TTOpt and baselines for HalfCheetah-v3 (N 3). The upper plot the average cumulative reward versus the number of interactions with the environment. The lower plot is the same versus execution time. The reward averaged for seven seeds. The shaded area shows the difference of one standard deviation around the mean. See similar plots for other environments in Appendix B.5.
To properly compare TTOpt with other methods, we propose modified evolutionary baselines that enforce constrained parameter domain. We adapt penalty term and projection techniques from 33 6 to introduce constraints, Appendix B.4 for details.
First, run benchmarks with small mode size N 3 with lower and upper grid bounds #1. Another series of experiments was done with finer mode of size N = 29 with the same bounds. These experiments model the case of neural networks with discrete (quantized) weights which use q-bits quantization, Finally, we provide the results of using TTOpt as fine-tuning procedure for linear policies from [36].
We present characteristic training curves based on the number of environment interactions and execution time for the HalfCheetah-v3 experiment (N = =3) in Figure Training curves for other environments can be found in Appendix B.5, in Figure 3 for N = and in Figure for N = 256. TTOpt consistently outperforms all other baselines on the coarse grid with mode size N Our method is still best for finer grids with mode size N = 256 on InvertedPendullum-V and and second-best on HalfCheetah-v3. Moreover, TTOpt has significantly lower execution time compared to evolutionary baselines. Another interesting observation is that the training curves of TTOpt have low dispersion, e.g., the algorithm performs more consistently than the baselines (see Appendix B.5). Table BabbleJssmmarize the experiments for the coarse and fine grids. Results for fine-tuning linear policies are presented Table in Appendix B.5. We also did rank and reward dependency study in Appendix B.
SaaallanddrCCntiuuuus.e
4 Related work
of the most advanced methods of black-box optimization. This approach aims to optimize the parameters of the search distribution, typically multivariate Gaussian distribution, to maximize the objective function. Finite difference schemes are commonly used to approximate gradients the parameters of the search distribution. Numerous works proposed techniques improve the convergence of ES [42] (65] proposed to use second-org natural gradient of [12] to generate updates, while (22) suggested include the history of recent updates generate next ones. 35 presented the concept of surrogate gradients for faster convergence.
In the case of high dimensional optimization, evolutionary strategies (ES) [56 42
Another series of works aimed reduce the high sampling complexity of ES. In [1 the thors described how to use active subspaces 14 to reduce the number of objective function calls dynamically.
Plenty the already mentioned works in gradient-free optimization specifically applied these methods to RL tasks
[53] 10
36 15 23 Overall, the performance of ES-based methods is comparable

---

to conventional policy gradients, especially if the number of model parameters is small [4 55 Another advantage of ES over policy gradient that it produces more robust and diverse policies by eliminating the problem of delayed rewards and short length time horizons. Finally, evolutionary approaches are suitable for the problems with non-Markovian properties
23
Other metaheuristic 225 38 and classical optimization [51] techniques are also studied within RL scope. The examples include simulated annealing 44. particle swarm optimization [24 33) and even
classical Nelder-Mead algorithm
4 43 These methods, however, are not tested on common RL
task sets. Several other works combined evolutionary methods with RL to achieve better performance
in complex scenarios 228 e.g., AlphaStar [62 33
Finally, low-rank tensor approximations have been applied to RL problems in settings different from ours, including multi-agent scenarios [34], and improving dynamic programming approaches [19
The idea of our method is quite different from the presented works, especially in the RI. area.
5 Conclusion
We proposed new discrete optimization method based on quantized tensor-train representation and maximal volume principle. We demonstrate its performance for analytical benchmark functions and reinforcement learning problems. Our algorithm is more efficient under a fixed computational budget than baselines, especially on discrete domains. Moreover, the execution time for TTOpt is lower by significant margin compared with other baselines. Finally, we show that the agents with discrete parameters in RL can be as efficient as their continuous parameter versions. This observation supports the broad adoption of quantization in machine learning. We hope that our approach will serve as a bridge between continuous and discrete optimization methods.
Acknowledgments and Disclosure of Funding
The work was supported by Ministry of Science and Higher Education grant No. 075-10-2021-068.
References
[1] Salman Ahmadi-Asl, Cesar F Caiafa, Andrzej Cichocki, Anh Huy Phan, Toshihisa Tanaka, Ivan Oseledets, and Jun Wang. Cross tensor approximation methods for compression and dimensionality reduction. IEEE Access, 9:150809- 2021.
[2] Stéphane Alarie, Charles Audet, Anmen E. Gheribi, Michael Kokkolaras, and Sébastien Le Digabel. Two decades of blackbox optimization applications. EURO Journal on Computational Optimization, 9: 9:100011, 1, 2021.
[3] Kai Arulkumaran, Antoine Cully, and Julian Togelius. Alphastar: An evolutionary computation perspective. In Proceedings of the Genetic and Evolutionary Computation Conference Com- panion, GECCO '19, page 314-315, New York, NY, USA, 2019. Association for Computing Machinery.
[4] Amir F. Atiya, Alexander G. Parlos, and Lester. Ingber. A reinforcement learning method based on adaptive simulated annealing. In 2003 46th Midwest Symposium on Circuits and Systems, volume 1, pages 121-124 Vol. 1, 2003.
[5] Pauline Bennet, Carola Doerr, Antoine Moreau, Jeremy Rapin, Fabien Teytaud, and Olivier Teytaud. Nevergrad: Black-box optimization platform. SIGEVOlution, 14(1):8-15, apr 2021.
[6] Rafat Biedrzycki. Handling bound constraints in CMA-ES: An experimental study. Swarm and Evolutionary Computation, 52: 100627, 2020.
[7] Alexey I. Boyko, Ivan V. Oseledets, and Gonzalo Ferrer. Tt-qi: Faster value iteration in tensor train format for stochastic optimal control. Computational Mathematics and Mathematical Physics, 61(5):836-88) 846, 2021.
[8] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. ArXiv, (iss1600.01554) 2016.
[9] Cesar Caiafa and Andrzej Cichocki. Generalizing the column-row matrix decomposition to way arrays. Linear Algebra and its Applications, 433(3):557-573,20) 2010.
10

---

[10] Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 970-978. PMLR, 10-15 Jul 2018.
[11] Krzysztof M Choromanski, Aldo Pacchiano, Jack Parker-Holder, Yunhao Tang, and Vikas Sind- hwani. From complexity to simplicity: Adaptive ES-active subspaces for blackbox optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buch E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[12] Andrzej Cichocki and Shun-ichi Amari. Adaptive Blind Signal and Image Processing; Learning Algorithms and Applications. John Wiley & Sons, Inc., USA, 2002.
[13] Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, and Danilo P. Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part low- rank tensor decompositions. Foundations and Trends@ in Machine Learning, 94-5):249-429 2016.
[14] Paul G. Constantine. Active subspaces emerging ideas for dimension reduction in parameter studies. In SIAM spotlights, 2015.
[15] Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via a population of hovelty-seeking agents. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18. page 0032-5043, Red Hook, NY, USA, 2018. Curran Associates Inc.
[16] Rémi Coulom. Reinforcement Learning Using Neural Networks, with Applications to Motor Control. PhD thesis, Institut National Polytechnique de Grenoble, 2002.
[17] Aleksandra Faust, Anthony G. Francis, and Dar Mehta. Evolving rewards to automate reinforee- ment learning. In 6th ICML Workshop on Automated Machine Learning, 2019.
[18] Sergei A Goreinov, Ivan V Oseledets, Dimitry V Savostyanov, Eugene E Tyrtyshnikov, and Nikolay I. Z.aaarashkin. How to find good submatrix. In Matrix Methods: Theory, Algorithums And Applications: Dedicated to the Memory of Gene Golub, pages 247-256. World Scientific, 2010.
[19] Alex Gorodetsky, Sertac Karaman, and Youssef Marzouk. High-dimensional stochastic optimal control using continuous tensor decompositions. The International Journal of Robotics Research, 37(2-3):340-317 377, 2018
[20] David Ha and Jürgen Schmidhuber. Recurrent world models facilitate policy evolution. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[21] Wolfgang Hackbusch and Stefan Kühn. A new scheme for the tensor representation. Journal of Fourier analysis and applications, 15(5):706-722. -2270, 2009.
[22] Nikolaus Hansen. The CMA Evolution Strategy: Comparing Review, pages 702 Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
[23] Verena Heidrich-Meisner and Christian Igel. Neuroevolution strategies for episodic reinforce- ment learning. Journal of Algorithms, 64(4):152-168, 2009. Special Issue: Reinforcement Learning.
[24] Daniel Hein, Alexander Hentschel, Thomas Runkler, and Steffen Udluft. Particle swarm optimization for generating interpretable fuzzy reinforcement learning policies. Engineering Applications of Artificial Intelligence, 65:87-98, 2017.
[25] Michael Herrmann, Adam Price, and Thomas Joyce. 3. Ant colony optimization and rein- forcement learning, pages 45-62. De Gruyter, 2020.
[26] John H. Holland. Genetic algorithms. Scientific American. 267 1992.
[27] Sebastian Holtz, Thorsten Rohwedder, and Reinhold Schneider. The alternating linear scheme for tensor optimization the tensor train format. SIAM Journal on Scientific Computing, 34(2)A683-A713, 2012.
11

---

[28]
Shauharda Khadka and Kagan Tumer. Evolution- -guided policy gradient in reinforcement learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 1196-1208, Red Hook, NY, USA, 2018. Curran Associates Inc.
[29] Boris N. Khoromskij. Ordlog quanttis approximation of n-d tensors in high- nigh-dimensional numerical modeling. Constructive Approximation, 34(2):257-280, Oct 2011.
[30] Tamara G. Kolda, Robert Michael Lewis, and Virginia Torezon. Optimization by direct search:
New perspectives on some classical and modern methods. SIAM Review, 45(3):385-45) 482, 2003.
[31] Oliver Kramer. A review of constraint constrainthhandling techniques for evolution strategies. Appl. Comp. Intell. Soft Comput. 2010, January 2010.
[32] Joel Lehman, Jay Chen, Jeff Clune, and Kenneth O. Stanley, ES is more than just traditional finite-difference approximator. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 18. page 450445444 457, New York, NY, USA, 2018. Association for Computing Machinery.
[33] Tundong Liu, Liduan Li, Guifang Shao, Xiaomin Wu, and Meng Huang. A Novel Policy Gradient Algorithm with PSO-Based Parameter Exploration for Continuous Control. Eng. Appl. Artif. Intell., 90(C), apr 2020.
[34] Anuj Mahajan, Mikayel Samvelyan, Lei Mao, Viktor Makoviychuk, Animesh Garg. Jean Kossaifi, Shimon Whiteson, Yuke Zhu, and Animashree Anandkumar. Tesseract: Tensorised actors for multi-agent reinforcement learning. In International Conference on Machine Learning
(ICMI.,, volume 139, pages 7301-7312, 2021.
[35] Niru Maheswaranathan, Luke Metz, George Tucker, Dami Choi, and Jascha Sohl- Sohl-Dickstein. Guided evolutionary strategies: augmenting random search with surrogate gradients. In Ka- malika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4264 4273. PMLR, 09-15 Jun 2019.
[36] Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[37] Erich Merrill, Alan Fern, Xiaoli Fern, and Nima Dolatnia. An empirical study of Bayesian optimization: Acquisition versus partition. Journal of Machine Learning Research, 22(4):1-25, 2021.
[38] Laurent Meunier, Herilalaina Rakotoarison, Pak Kan Wong, Baptiste Roziere, Jérémy Rapin, Olivier Teytaud, Antoine Moreau, and Carola Doerr. Black-box optimization revisited: Im- proving algorithm selection wizards through massive benchmarking. IEEE Transactions on Evolutionary Computation, pages 1-1,2021. 2021.
[39] Aleksandr Mikhalev and Ivan Oseledets. Rectangular maxiimum-volume submatrices and their applications. Linear Algebra and its Applications, 538:187-211, 2018.
[40] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 5 518(7540):529-533 Feb 2015.
[41] John A. Nelder and Roger Mead, A simplex method for function minimization. Computer Journal, 7:308-313, 1965.
[42] Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):27-5666, Apr 2017.
[43] Barry D. Nichols. Continuous action-space reinforcement learning methods applied to the minimum-time swing-up of the acrobot. 2015 IEEE International Conference on Systems, Man, and Cybernetics, pages 2084-2089, 2015.
[44] Alexander Novikov, Maxim Rakhuba, and Ivan Oseledets. Automatic differentiation for Riemannian optimization on low-rank matrix and tensor-train manifolds. SIAM Journal on Scientific Computing, 44(2) 2022.
12

---

[45] Ivan V Oseledets. Approximation of 2d x 2d matrices using tensor decomposition. SIAM J.
Matrix Anal. Appl., 31(4):2130-2145, 2010.
[46] Ivan V Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing,
33(5):2255-2317, 2011.
[47] Ivan V Oseledets and Eugene E "Tyrtyshnikov. Breaking the curse of dimensionality, or how to use SVD in many dimensions. SIAM Journal Scientific Computing. 31(5)3374--3759, 2009.
[48] Ivan V Oseledets and Eugene E Tyrtyshnikov. TT-cross approximation for multidimensional arrays. Linear Algebra and its Applications, 432(1):70-33) 2010.
[49] David Pfau, James S. Spencer, Alexander G. D. G. Matthews, and W. M. C. Foulkes. Ab initio solution of the many-electron schrödinger equation with deep neural networks. Phys. Rev. Research, 2:033429, Sep 2020.
[50] Anh-Huy Phan, Andrzej Cichocki, André Uschmajew, Petr Tichavský. George Luta, and Danilo P. Mandic. Tensor networks for latent variable analysis: Novel algorithms for tensor train approximation. IEEE Transactions on Neural Networks and Learning Systems, 31(11):4622 4636, 2020.
[51] Zhiwei Qin, Weichang Li, and Firdaus Janoos. Sparse reinforcement learning via convex optimization. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 424 432, Bejing, China, 22-24 24 Jun 2014. PMLR.
[52] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. ArXiv, abs/2102.12092, 2021.
[53] Tim Salimans, Jonathan Ho, Xi Chen, and Ilya Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. ArXiv, abbb/1703.03644 2017.
[54] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz, Trust region policy optimization. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1889,1897, Lille, France, 07-09 Jul 2015. PMLR.
[55] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, abs/1 .06347, 2017.
[56] Hans-Paul Schwefel. Evolutionsstrategien für die numerische Optimierung, pages 123-176. Birkhäuser Basel, Basel, 1977.
[57] Artur M. Schweidtmann and Alexander Mitsos. Deterministic global optimization with artificial neural networks embedded. Journal of Optimization Theory and Applications, 180(3):925
Oct 2018.
[58] Alexandra Senderovich, Ekaterina Bulatova, Anton Obukhov, and Maxim Rakhuba. Towards practical control of singular values of convolutional layers. In Advances in Neural Information Processing Systems, 35, 2022.
[59] Rainer Storn and Kenneth Price. Differennial evolution a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4)331-339, Dec 1997.
[60] Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Deep neuroevolution: Genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning. ArXiv, abs/ libs/1772.06667, 2017.
[61] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033, 2012.
[62] Oriol Vinyals, Igor Babuschkin, Wojeiech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre,, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander S. Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKin- ney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris
13

---

Apps, and David Silver. Grandmaster level in StarCraft II using multi-agen reinforcement learning. Nature, 575(7782)3350-554 Nov 2019.
[63] Lev Vysotsky and Maxim Rakhuba. Tensor rank bounds and explicit qut representations for the inverses of circulant matrices. arXiv preprint arXiv:2205. 04335, 2022.
[64] Pawel Wawzzynski. Learning to control 6- of-freedomm walking robot. In EUROCON
2007 The International Conference on "Computer as a Tool", pages 698-705, 2007.
[65] Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. Journal of Machine Learning Research, 15(27):949-980, 2014.
[66] Qibin Zhao, Masashi Sugiyama, Longhao Yuan, and Andrzej Cichocki. Learning efficient tensor representations with Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8608-8612 8612, 2019.
networks. In ICASSP 2019 2019 IEEE International
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The work has no any societal impacts, since its about optimization methods.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The code will be provided in supplemental material and as github repository after decision
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We used a typical shade(mean-stee plots that used in reinforcement learning experiments
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]. We mentioned all references and source-codes for gradient-fre free baselines.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you' 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xrM4jNQf70T", "reviewer": "Reviewer_uApo", "summary": "The paper presents a gradient-free optimization method, based on the tensor train approximation of the functional and the maximum volume principle, adapted to navigate the optimized parameter space instead of reconstructing the volume. Experiments on multidimensional analytical functions and reinforcement learning settings demonstrate superior convergence rates and efficiency in terms of calls to the black-box function.", "questions": "1. L47 \"Our algorithm can directly train quantized neural networks\" - can the authors explain this? I understand the concept of QTT, but this point is only seen in the introduction and slightly touched around the RL part. Also, L235 \"These experiments model the case of quantized neural networks which use q-bits quantization.\" - please elaborate on how NN parameter quantization relates to TT mode quantization.\n2. In relation to Table 3, please discuss why some environments benefit from finer quantization while others don't, especially given the low variance of curves?\n3. What are the convergence guarantees of TTopt?\n4. The paper mentions \"up to machine precision\" (L40), and by the look of fp exponent of results in Table 1 and on, single-precision was used. Do the results improve further with double precision?\n5. In Algorithm A1, rank selection only accounts for the left-hand side constraint on the ranks but does not enforce the right-hand side constraint. Shouldn't it also be the $\\min(R_{i-1} N_i, R_i N_i, r_{max})$? This obviously cannot be done in a single loop due to double-side recursion; however, two loops can do. Wouldn't it be better than the reduction procedure from LL58-61 of the supplementary?\n6. In Algorithm A1, \"Set $G_i = \\mathrm{random}(R_i N_i , R_{i+1})$, random how? Does the distribution matter?\n7. Why is the case of linear policies important to consider TTopt with?\n\nWriting tips:\n- Order of environments in the left and right parts of Table 3 is different for no good reason\n- Consider enabling line numbering built into algorithmicx for ease of referring to line numbers\n- Annotating algorithms with shapes of operands would help in understanding\n- Consider prioritizing a self-contained intro into the experimental domains and smooth explanation of TTopt plugging into the big picture, over explanations of TT and maxvol, provided that the main paper cannot fit the core algorithms anyway due to limited space.", "limitations": "Answers to several questions asked above, in combination with the rather deep analysis of rank and number of evaluation dependencies,  cover the most interesting limitation scenarios.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Judging by the provided analysis and results, TTopt deserves membership in most gradient-free optimization toolboxes.\nExtending maxvol principles for optimization and mandatory quantization of the continuous case are interesting, novel, and significant (conditioned on the presented results).\nThe study of TTopt on analytical functions is rich and deep, going as far as comparing with Bayesian optimization methods.\n\nHowever, given the impressive results from Fig.3 in RL environments, too little space is allocated to explaining the setup and discussion of what makes two orders of magnitude improvement in reward possible. \nAdditional explanations in the supplementary are helpful but do not leave the impression of self-contained work. Domain expertise in RL and evolutionary strategies is required to understand the paper. The paper would benefit from a brief recap of ingredients and an explanation of how TTopt plugs into the RL pipeline. The MDP formalism (B.3) does not elaborate on whether the setup is applicable in off-policy /on-policy settings, whether it makes sense to optimize the number of evaluations, and whether all requested evaluations can always be carried out. \nDiscussion of what entails exceeding the target reward is missing.\n\nThe paper is well-written and mainly easy to follow, except for frequent redirections to the supplement and related work for specific and essential parts of the narrative. Perhaps pivoting some text from pages 3 and 4 into the supplement won't hurt and would allow for streamlining the \"story\" since understanding the concepts of the tensor train decomposition does not really help to understand what is under the hood of TTopt without going into the supplement. In a sense, the matrix case (very well-written) is not representative of the multi-dimensional case due to many special handling bits.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Y0Y0gy2pAo6", "reviewer": "Reviewer_Aky3", "summary": "The authors present a novel approach to multivariate optimisation of general objective functions making use of tensor-train decompositions over discrete state-spaces.   The TT Decomposition approximation is based on the cross-approximation method / TT-Cross of Oseledets, etc.   The main interest to use TT-cross is not for building a approximation but based on the observation that maximal elements of the tensor are highly likely to be in the maximum volume submatrix which is found using MAXVOL in TT-cross and the maximal element of\nthe sub-matrix increases monotonically over the iterations.    This result is hinted at, but unless I misunderstand, it is not proved or confirmed.  This is employed empirically to define a new optimisation algorithm.\n\nThe algorithm is deployed in the context of Reinforcement learning, as an alternative to evolutionary approaches, as well as some general optimisation baseline examples.  It is demonstrated that the method is competitive, and in many cases outperforms other approaches.", "questions": "* Why are the authors specifically considering RL as a test case for this method?  This seems to be shoe-horned in.  I don't see any necessary need for such non-differentiable optimisation methods, whereas I can think of many other situations involving high-dimensional non-differentiable objective functions.  I appreciate the motivation based on Saliman's work on Evolutionary algorithms in RL, but this seems tenuous.   Can the authors shed some light about why this is the *right* method for RL and when?  It seems that for all of the presented problems, policy gradient would've worked just fine.\n\n* The key assumption in the proposed iterative optimisation method is that the maximum volume sub-matrix should contain the absolute maximum element, thus justifying the iteration.   However, unless I misunderstand, this isn't justified by any argument provided in this work, including the \"intuition behind ttopt\" presented in page 3.   I really think this needs to be studied more, because this is a crucial feature that needs to be justified.   I appreciate that this can be quite a challenge, but some intuition about why this property should be true is important.", "limitations": "I think the authors need to be a bit clearer about what can and cannot be guaranteed with this methodology.  It is ok if the method is heuristic but this needs to be made very explicit.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* (Originality) This work presents an interesting approach to optimisation of (possibly non-differentiable) high-dimensional functions, exploiting tensor train decompositions, which is novel.\n* (Significance) This is important as the traditional approaches to high-dimensional gradient free optimisation (e.g. BO) do not necessarily scale well with dimension, so that this offers a plausible alternative.\n* (Quality) The paper is generally well written.\n\nWeaknesses:\n* (Clarity): I do not understand why the authors felt the need to bring reinforcement learning into this work.  The TTOpt algorithm is a general purpose optimisation algorithm, it is unclear why the authors felt that RL would be a unique use-case for this method, particularly given that the examples studied do not appear to involve non-differentiable loss-functions, and moreover, could be solved using policy gradient approaches.    This feels quite odd to me.\n* (Significance) The key assumption in the proposed iterative optimisation method is that the maximum volume sub-matrix should contain the absolute maximum element, thus justifying the iteration.   However, unless I misunderstand, this isn't justified by any argument provided in this work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "F7693w2o3n4", "reviewer": "Reviewer_WXFn", "summary": "The paper proposes an optimization method for multivariate functions of discrete arguments by considering their low-rank tensor decomposition in terms of Tensor Train structure. The method is compared to gradient-free methods, and is evaluated on Reinforcement Learning tasks and on functions with continuous arguments.", "questions": "* Questions \n\t- Maximum Value in matrix is bounded by $\\hat{J}_{max} \\geq \\frac{J}{R^2}$, for tensors with $d$ indices, would this bound grow to the power of $d$, doesn't this bound increase with the compression trick? \n\t- What happens when you have a tensor train of $d=2$, where there are two minimal values of $-1$ in each, and a maximal value of $0.5$ in each? the total maximal value is $1$, isn't it? (The mapping function in equation 7 is applied at the end)\n\t- Why are the values in Table 2 in the appendix are of order of magnitude different than presented in Table 1 of the main text? of instance, the absolute deviation from the minimum of the Ackley function is $1.2$ (the absolute minimum is at $0$), but the relative deviation is $3.9e-6$.\n    - It seems all the test functions have the symmetry of $x_i \\rightarrow -x_i$. How would the method work for non-symmetric test functions?\n   \n\n* Suggestions\n\t- Perhaps add the definition for \"Maximum modulus element\" to the main text.\n\t- Perhaps add an evaluation of the method with the compression to modes and without (line 178).\n\t- It would be interesting to see how the approach handles non-differentiable functions as it is gradient-free.\n\t\n\t\n* Minor corrections:\n  - line 181 \"Let assume\" -> Assume that\n  - Appendix Table 2 Grienwank -> Griewank", "limitations": "* I believe that when the method is applied to continuous functions, it is sensitive to the chosen discretization grid. Moreover, the complexity of the method increases for finer grids, as the $N_k$ increases.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main text is clear and well written. This work combines various solutions to solve this optimization problem, that is, extending the maxvol function to higher order tensors, replacing high dimensions by decomposing them to lower ones, and applying an updated mapping function to deal with algorithmic constraints. Additional experiments  testing different hyper-parameters appear in the appendix. The paper lacks, however, experiments that demonstrate the contribution of each individual part of the method empirically, such as the mapping function and the mode compression.\n\nIf the landscape of RL consisted of only of gradient-free methods, then the presented low execution time of the method, together with its ability to solve the problems successfully, makes this work significant. The fact there is no comparison to gradient-based methods is a major weakness and complicates the assessment of the possible impact of this work.\n\nStrengths:\n* Extends a matrix-based method to higher order tensors.\n* Low execution time in comparison to other gradient-free approaches.\n* Various experiments regarding the hyperparameters of the method appear in the appendix.\n\nWeaknesses:\n* No comparison with gradient-based methods.\n* The comparison to RL is lacking. There is no comparison to any gradient-based method.\n* There are no ablations to the benefits of using either the mapping functions (Eq. 7) or mode compression.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "B6tHEXKhuFw", "reviewer": "Reviewer_g4hT", "summary": "This paper implements a novel method to find maximum elements of a tensor-shaped object function by combining quantized tensor train representation and generalized maximum matrix volume principle. The author applied this method to minimization of multidimensional functions and reinforcement learning tasks.\n", "questions": "1. The quantized Tensor train seems inconsistent with the subsection 2.4. The searching submatrix is R*R, but when the tensor is quantized to a 2-power tensor, usually R should larger than 2, thus there should be some initial step to start the algorithm.\n\n2. As stated in line 137 and 129, each maxvol algorithm are worked in a reshaped submatrix with coloum indices randomly choosed. However, the author declare that the the algorithm will  converge to optimal row and coloum indice, which seems strange.", "limitations": "Comparison against bayesian optimization which is also a brunch of methods for black box optimization is missing in the paper.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe originality is good. The algorithm combining Tensor-train and maxvol algorithm is novel and clear. The writing quality is good. The complexity is also analysed. It should be a significant work if it can work well on a wide range of tensor-shaped object function.\n\nWeekness:\nOn theoretical aspect, there are no guarantee on the stability nor convergence of the algorithm. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept