Generalized Policy Iteration using Tensor Approximation for Hybrid Control
Authors: Suhan Shetty
Teng Xue
Sylvain Calinon
Venue: ICLR 2024 spotlight (2024)
Keywords: Optimal Control
Hybrid Actions
Robotics
Approximate Dynamic Programming
Tensor Approximation
Primary area: applications to robotics, autonomy, planning
TL;DR: The paper proposes a novel approximate dynamic programming algorithm that can handle hybrid action space

Abstract: Control of dynamic systems involving hybrid actions is a challenging task in robotics.  To address this, we present a novel algorithm called Generalized Policy Iteration using Tensor Train (TTPI) that belongs to the class of Approximate Dynamic Programming (ADP). We use a low-rank tensor approximation technique called Tensor Train (TT) to approximate the state-value and advantage function which enables us to efficiently handle hybrid systems. We demonstrate the superiority of our approach over previous baselines for some benchmark problems with hybrid action spaces. Additionally, the robustness and generalization of the policy for hybrid systems are showcased through a real-world robotics experiment involving a non-prehensile manipulation task which is considered to be a highly challenging control problem.

Published as a conference paper at ICLR 2024
GENERALIZED POLICY ITERATION USING TENSOR APPROXIMATION FOR HYBRID CONTROL
Suhan Shetty Teng Xue!?, Sylvain Calinon
Idiap Research Institute. Martigny, Switzerland
2 École Polytechnique Fédérale de Lausanne (EPFL), Switzerland name , surname @idiiidiiis diap.
ABSTRACT
Optimal Control of dynamic systems involving hybrid actions is a challenging task in robotics. To address this, present novel algorithm called Generalized Policy Iteration using Tensor Train (TTPI) that belongs to the class of Approximate Dynamic Programming (ADP). We low-rank tensor approximation technique called Tensor Train (TT) to approximate the state-value and advantage function which enables us to efficiently handle hybrid action space. We demonstrate the superiority of our approach over previous baselines for some benchmark problems with hybrid action spaces. Additionally, the robustness and generalization of the policy for hybrid systems are showcased through a real-world robotics experiment involving a non-prehensile manipulation task.
Robotic systems often exhibit complex nonlinear dynamics that may involve hybrid actions. The need for real-time control, high precision, and adequate robustness to cope with disturbances or changes in the environment can result in demanding computational requirements that are challenging to meet with classical control methods. Optimal Control (OC) based on the principles of Dynamic Programming (DP) is popular tool in robotics but they are still limited to systems with continuous actions and differentiable dynamics.
Approximate DP (ADP) and Reinforcement Learning (RL) overcome the curse of dimensionality faced by classical DP algorithms by using function approximation techniques (Sutton & Barto, 2005; Bertsekas, 2012). OC is closely related to ADP and uses the system's 's model to obtain an optimal policy, while RI. focuses on learning a policy through trial-and-error interactions with the environment, Both methods aim to find a compact representation of the value functions to obtain a control policy. ADP faces difficulty in approximating the value function throughout the entire state space, conversely, RL restricts its approximation to a smaller region where data is collected, resulting in limited generalizability but greater scalability. However, the existing approaches for both ADP and RL face challenges in handling hybrid action space. Furthermore, existing ADP approaches also find it challenging to cope with large action spaces and hybrid states.
In this paper, we present a novel ADP algorithm, called Generalized Policy Iteration using Tensor Train (TTPI) which overcomes the challenges faced by existing ADP methods for hybrid system control. TTPI is an approximate version of the Generalized Policy Iteration (GPI) algorithm-a DP algorithm that encompasses both Value Iteration (VI) and Policy Iteration (PI) algorithms. We use Tensor Train (TT) (Oseledets, 2011), a low-rank tensor approximation technique (Grasedyck et al., 2013), to model the state-value and the advantage function.
TT is versatile function approximator that allows us to simultancously handle continuous and discrete state and action variables. approximates given function as a sum of products of univariate functions, allowing for fast algebraic operations and interpretation. The use of TT-Cross (Oseledets & Tyrtyshnikov, 2010; Savostyanov & Oseledets, 2011), a powerful gradient-free method to approximate functions in TT format in nonparametric manner, allows us to achieve TT approximation of state- value and advantage function with a desired accuracy in a fast manner, thus exploiting the knowledge of the system model and the reward function. Moreover, the TT representation of the advantage function enables us to use optimization techniques such as TTGO (Shetty et al., 2023) to retrieve policies for hybrid action spaces.

---

Published as a conference paper at ICLR 2024
The TT representation is particularly effective when the function being approximated is smooth, resulting in a low-rank representation in the TT format. Our experiments demonstrate that such property is frequently observed in ADP while dealing with hybrid systems. Indeed, even though the system dynamics and reward functions may be non-smooth and discontinuous, the optimal value functions typically exhibit low-rank structures.
Contributions:
We introduce TTPI, a novel ADP algorithm for optimal control that leverages TT as a function approximator address the challenges of hybrid system control in robotics. Our approach is interpretable and eliminates the need for differentiability of the system dynamics and reward function which is a common assumption the existing ADP algorithms. Our experiments demonstrate that TTPI outperforms state-of-the algorithms in terms of both training time and performance on various benchmark control tasks for hybrid control. To showcase the practicality and generalization of our approach, we conducted real-world robotic experiment where we successfully tackled non-pon non-prehensile planar manipulation task that notoriously difficult for existing control methods. Our results demonstrate the robustness of the policy and highlight the potential of our approach to addressing complex control problems in robotics.
GENERALIZED POLICY ITERATION USING ADVANTAGE FUNCTION
1.1 THE OPTIMAL CONTROL PROBLEM
We consider discrete-ting time dynamic system with d-dimensional state space and m-dimensional action space. For ease of presentation, we assume the dynamic system to be deterministic, however, our approach can also handle stochastic model (see Section 2.9).
We denote the state at time t by (s!....,s#)) of the system given by
and action by a2 (a.,..., .("".. The dynamics .44)
8111 [(8,, az): s.t. 8 agi, vi (1,...,dh) Ea Vj E {l..... m,)
where the domain of each state 2g and action Qa can be bounded real interval or discrete set. Let S2 denote the state space and Qa denote the action-space.
Let rss, a) represent the reward function and A be the time step for the discrete-time control. We define R(s, a) = r(s, a) At. Our goal is to obtain an optimal policy x for the following infinite horizon optimal control problem for any given initial state in the state space so Ωg.
oo
arrgmam max
7 R(s,, ((s)), Asp
with 8141 [(s, (8:)),
where y is the discount factor 0 < < 1.
We do not make any assumption on the structure or differentiability of the dynamics f and the reward function r. For example, a black box deterministic simulator that returns the next state and the reward for the state-action pair satisfies our requirement. However, for fast implementation of our algorithm described in Section 2.8, the simulator should ideally process batch of state-action pairs for parallel implementation.
1.2 DYNAMIC PROGRAMMING The mate-value function V corresponding to a policy æ, with discount factor 7, defined as
(*((n)
7 R(si, T (8t)), Vso.
1
where
8141 = f(s,, π (8:)), Vt.
Given state-value function V Ω2 R, policy and the discount factor the Bellman operator TTT functional that is defined as B= Vs) = R(s, T()) (V((s (()))) Vs e Q2 where 1T V + V.
2

---

Published as a conference paper at ICLR 2024
We define the advantage function Av corresponding to the value function V as (v a) R(s, a) + r (V((s,))) - -V(s), v(s, a) E Us x Sta
(4)
1.3 CHALLENGES IN APPROXIMATE DYNAMIC PROGRAMMING
Algorithm describes the value iteration (VT) al- gorithm (Sutton & Barto, 2005). a popular DP algorithm.
Algorithm VI Algorithm
Input: Initial value function VO, conver-
One of the challenges in implementing the VI al- gorithm and other similar DP algorithms including the Policy Iteration (PI) algorithm (Sutton & Barto, 2005) in practice is the curse of dimensionality in representing the value function when the involved state space is either nigh-dimensional includes continuous states. ADP addresses this challenge by using function approximation techniques.
gence threshold
Output: Optimal policy n
Set k =
2: repeat
n =*() arg max Ava
V++1 B B
5:
if [[]]k - V= < then
In addition, retrieving the policy x² from the ad- vantage function is difficult if is nonconvex, if there are bounds on the actions, if the action space large, or if the action space is hybrid. An inef- ficient optimization technique for policy retrieval increases the overall time of the algorithm, as must be repeated for each state in every iteration, and it results in sub-optimal policy. The lack of such policy retrieval techniques is bottleneck in the development of ADP algorithms for hybrid control.
break end if
7:
Set k k
9: until convergence
10: V ===v
11: x² x²(8) = arg max (s)
GENERALIZED POLICY ITERATION USING TENSOR TRAIN (TTPI)
In this section, we briefly describe the proposed approach and the related concepts used to tackle the previously described challenges in ADP for handling hybrid actions and large action spaces. Further details are provided in the Appendix. In summary, we overcome the challenges mentioned in the ADP algorithms using TT as function approximator. We propose to model the advantage function explicitly in TT format and use TTGO, a technique for optimization of functions in TT format proposed by Shetty al. (2023); Chertkov al. (2022), for policy retrieval.
2.1 TENSORS AS DISCRETE ANALOGUE OF A FUNCTION
multivariate function P(æ1...... .....))))) defined over rectangular domain made up of the Cartesian product of intervals (or discrete sets) I x ... x Is can be discretized by evaluating it at points in the is
set X' = {(
I E 14, is E {l,..., "l,...,,xh! This gives us a tensor P, discrete version of P. where P (e).....d)) 4d) P(a ..... ..f .f)),
V(i.. (d) E Zx, and Ix = (ii,...., f2) ig (1...., ....,,.).. ], k E (1...,,, d}} }. The value of P at any point in the domain can then be approximated by interpolating between the elements of the tensor P.
2.2 TENSOR DECOMPOSITION Representing high- digh-dimensional tensor is difficult because of the limitation in storage. Tensor decomposition techniques (Kolda & Bader, 2009; Sidiropoulos et al., 2017) solve this problem by representing the tensor using a smaller number of fower-dimensional tensors, known as factors, which occupy less memory. These factors are combined with certain algebraic operations, depending the decomposition method, to represent the elements of the original tensor. addition to the compact representation, they also enable efficient algebraic operations in the compressed format.
The accuracy tensor representation is usually controlled by its rank the decomposition, which is proportional to the number of elements in the factorization. The rank of the tensor is closely related to the separability of the underlying function. In practice, for continuous variables, the smoothness of the underlying function often corresponds low rank.
3

---

Published as a conference paper at ICLR 2024
2.3 TT DECOMPOSITION TT decomposition, also known as Matrix Product State (MPS) or Tensor Networks (TN) in physics (Cichocki et al., 2016). is widely used tensor decomposition technique due its versatility and effective methods for determining the approximation.
2D
Figure 1: TT decomposition extends ma- trix decomposition techniques to arrays with higher dimensions. In matrix decomposition, an element in the original matrix can be ob- tained by multiplying the appropriate rows or columns of the factors. Likewise, an element in a tensor represented in TT format can be retrieved by multiplying selected slices of the core tensors, which are the factors. The il- lustration shows examples of 2nd, 3rd, and 4th-order tensors.
P
P
Pi
P
P
P R Kagann pe
P PurtA
P
Pins
P
TT decomposition approximates given tensor (a multidimensional array) compactly using set of third-order tensors called cores. A d-th order tensor P E I X.xnng TT format is represented using tuple of d third-order tensors "P.....,""' )d)) The dimension of the cores are given as p E I. 11xx xn, pk E R=*-1xm= Xra, A E (2,...,--11 d- I. and pd E Bra- xnax1 with = Ta 1. As shown in Figure I, we can access the element (i,,...,id) id) of the tensor in this format simply given by multiplying matrix slices from the cores
P (i) P P. :.i..:
P.. Siae::
(5)
where P.... R 1X's represents the ég-th frontal slice (a matrix) of the third-order tensor pk The dimensions of the cores are such that the above matrix multiplication yields a scalar. The TT-rank of the tensor in TT representation is then defined as the tuple = (r1, (2,,/,,...... ra-1i) We call r = max (fi,..., 1d-1) as the maximal rank. For any given tensor, there always exists TT decomposition (5) (Oseledets, 2011).
2.4 TT-CROSS
TT-Cross (Oseledets & Tyrtyshnikov, 2010: Savostyanov & Oseledets, 2011) efficiently computes 'T approximation of tensor with controlled accuracy by evaluating only small number of its elements, without requiring the entire tensor to be stored in memory. does this by computing only specific tensor fibers at time, in black-box manner. A noteworthy feature of TT-Cros is that is an unsupervised and nonparametric approach as it directly takes the function being modeled as its input and the number of parameters in its TT representation is adjusted based on the structure of the underlying function until a specified accuracy of the approximation is obtained.
Consider tensor P that is discrete analog of function P with domain Ω using discretization set Ω. Instead of evaluating the entire tensor, TT-Cross selects a subset of elements by evaluating function P at various points in the discretization of Ω The approximate tensor in TT format, P TT-cross P, ②2, Fmax; G) requires only (ndr²2) evaluations, rather than ((n)) evaluations of the full tensor. Here, Fmax is the approximation, and r is the actual rank of the tensor in TT format. TT-Cross is efficient when the TT-rank is low, which is often the case for state-value functions in many problems involving hybrid states. We can then obtain the continuous approximation to P from P using (7).
C,),
bound on the rank of the TT, is the accuracy of the
2.5 ALGEBRAIC OPERATIONS IN TT FORMAT
In addition to representing tensor compactly, the TT format enables the efficient execution of various tensor algebraic operations its compact form. Operations such as addition, subtraction, and inner product of TT tensors be performed efficiently (Lee & Cichocki, 2018). The mean, norm, and gradient can also be calculated efficiently. The compactness of the representation can be improved by using TT-rounding operations, with a trade-off in accuracy. The availability of these
4

---

Published as a conference paper at ICLR 2024
algebraic tools allows thorough analysis of the functions represented in TT format, thus making them highly interpretable.
2.6 CONTINUOUS APPROXIMATION USING TT
Given the discrete analogue tensor P of a function P. we obtain the continuous approximation by spline-basse interpolation of the TT cores corresponding example, we can use linear interpolation for the cores (i.e., between the matrix slices of the core) and define matrix-valuse function corresponding to each core & E { {1.....d}
the continuous variables only. For
I +++1
P* (*x)
PM
+ +++1 Ik
Ikk pk
(6)
i++1
2g
2k
where x 2h S ox and pk 1s IR continuous approximation of P given by
R X with ro ra 1. This induces
P( P(a
va) R P (o)) (ara)
This allows selectively do the interpolation only for the cores corresponding to continuous
variables, and hence we can represent functions in TT format whose variables could be a mix of continuous and discrete elements.
We overload the terminology to define the continuous TT representation as p Zki = =P*)))
P x = P P Ia), where æ = (I1,.... Id),
(8)
P
P.d ia Vzg Oza Vk E (I.
2.7 TTGO: OPTIMIZATION OF FUNCTION IN TT-FORMAT
In addition to the availability of algorithms like TT-Cross for finding function approximation and the accompanying algebraic tools, advantage of using TT decomposition for approximating functions in ADP is its ability to efficiently find optima over a mix of continuous and discrete variables. This was introduced as Tensor Train for Global Optimization (TTGO) in Shetty et al. (2023), in the form of a stochastic method. deterministic version of this was proposed in Chertkov et al. (2022). We propose improvements to this approach in this paper, see Section A.9 in Appendix. In practice, the technique often yields globally optimal solutions, as demonstrated in Shetty et al. (2023) and Chertkov al. (2022).
The basic idea behind TTGO is that it transforms the given function in TT format, using the accompanying necessary algebraic tools, into nonnegative function in TT format that can be interpreted as probability density function. The efficient sampling techniques for density functions in TT format allow us to pick samples of only high-density regions which turn correspond to the optima. In practice, the chosen number of prioritized samples N > and the sample(s) with the highest density (or least cost) is used represent the optima. The solution obtained from such procedure can be refined further using local optimization techniques such as Newton-type optimization for continuous variables. But, in practice, as this paper, the fine-tuning is often not required.
In this paper, we identify and exploit TTGO's ability to handle a mix of continuous and discrete variables. In addition, perform optimization in the batch form: we propose model the advantage function A(s, a) ADP TT format, and adapt TTGO to obtain the optimal actions a corresponding batch of states s (i.e. parallel computation of arg max A(s, a)) in efficient manner.
2.8 TTPI ALGORITIM
By combining the conceptual ideas proposed far, Algorithm presents the TTPI algorithm, which addresses the previously mentioned challenges in ADP using TT as the function approximator for state-value and advantage functions and TTGO for policy retrieval.
In the TTPI algorithm, the value update step involves computing (s) (i.c., arg max, Ays (s, a)) numerous times across several iterations. To compute V in TT-format, the function T B Vik is queried iteratively using TT-Cross(B V T), with batches of states (usually ranging from 10,000 to 100,000 in practice). This requires computing the policy Th for each of these states in batch form. We use TT-round to compress the value functions in TT format at the end of every policy
5

---

Published as a conference paper at ICLR 2024
evaluation (i.e., after updating the value function for the current policy). We cubic spline- ppsene-based interpolation for continuous variables which reduces the number of discretization points required by TT-cross to construct the TT model.
To resolve the bottleneck in policy retrieval, we propose to compute the advantage function Ave in TT format using TT-Cross. This is efficient the calculation only requires evaluating V and R(s, a), which are cheap to compute. This enables the numerical optimization of variables for functions in TT format using TTGO, as outlined in Section 2.7. As result, π <²(s) over batches of states can be obtained quickly. Most importantly, this allows us to handle hybrid action space. The computational cost involved in retrieving a solution is O(Nmdr' max) which is linear in the number of discretizations (d) of an action variable and the dimension of action space (m).
The computational cost of the algorithm increases linearly with the number of dimensions in both state and action spaces and grows quadratically with the rank of the functions represented TT format, thanks the properties of TT-Cross and TT-representation. A PyTorch-based GPU- accelerated implementation of these algorithms is provided along with the supplementary material at http:://stes.. hutps//sites.google.coom
2.9 TTPI FOR STOCHASTIC SYSTEMS
In this section, we show how our approach can be extended to consider stochastic system dynamics. Instead of relying on deterministic system dynamics of the form s' = f(ss, a), we consider the transition probability P(s', 8, a) and the reward function R[s,, a) in TT format. The transition probability P(s', 8, a) can be obtained by fitting density model to data collected from the robot. To achieve this, we can employ the TT format for density modeling as suggested by Novikov et al. (2021) and Han et al. (2018). Alternatively. if the function P is available in different format such as NN, we can utilize TT-Cross. By leveraging the algebraic tools provided in TT format, we can normalize P such that En P(s', 8, a) 1 (or integrate if s' is continuous). The following outlines the procedure to update the value function and policy under this approach: V =TT-Cross(U* Ωi Fmax, c),
UK (s) R(s, T (s)) + + (s (s)).
(8 a) Σ P(s' s, a))
Av* a) R(s, + >( a) (*)),,
n² **(ss) arg max Avx (s. a).
In the above algorithm, P and V are both in TT format, algebraic operation over TT format (namely, element-wise product and contraction operations over 8'). Then Aya can be readily computed TT-format using addition operations over the TT tensors as R. W and V are also in TT format. We only need TT-cross to find V*k Hence the algorithm would be very efficient if P is known in TT format. However, we acknowledge that, practice, obtaining a stochastic model of system P from data is challenging problem and it is still an ongoing area of research.
obtain W efficiently by using
EXPERIMENTS
In our experiments, we utilized an NVIDIA GeForce RTX 3090 GPU with 24GB of memory. For the applications considered, we discretized each continuous variable with 100 points using uniform discretization. To approximate the value and advantage functions in TT format using TT-Cross, an accuracy of e = 10 - proved sufficient. We set Fmax to a large value 100. The discount factor was chosen in the range of 0.99 0.9999, depending 0.001. The rank of the value function in the applications considered ranged between to 50, and the rank of the advantage function was roughly twice that of the value function.
the time step At which ranged from 0.01 to
3.1 SIMULATION EXPERIMENTS:
Baseline: To the best of our knowledge, there established approaches for OC based ADP algorithms that can handle hybrid actions. To evaluate our algorithm performance, we compared against Deep RI. techniques for hybrid action spaces such HyAR, HPPO and PDQN (Li et al.,

---

Published as a conference paper at ICLR 2024
Algorithm 2 TTPI: Generalized Policy Iteration using Tensor Train
Input:
Output: Policy π
ny: Number of value update steps
1: while d < 6max do
e: *Accuracy of TT representation
2:
k = k +
Tmax: Maximum TT-rank
3:
T (8)) == argmax A (8 (Use TTGO)
mmax: Convergence tolerance
r(8, a): Reward function
4:
At: Time Discretization
5:
for < 1 to n. do
f(s, a): Forward simulation
V (s) TT-Cross(B* V.E. 1= Sux mmax:: E)
Q2g: Discretization of state space
7: end for
Q: Discretization of state-action space
V
TT-round V..
( x Sia)
A ( a) R(s, +7 (
(s.
N: Number of candidate samples for op-
tima used in TTGO.
10:
Av* = IT-Cross(AA 2 rmax, c)
Initialize:
1: Initialize 100 in TT-format
11:
||VA-1|12
2: Initialize Advantage model:
12: end while
13: Set V* = V
3: Avo = TT-Cross( R(s, a),, 9t Tmax, s)
14: iT" (8) = argmaxAy-
4: (alternatively, initialize arbitrarily),
5: Set k:
Figure 2: The tasks considered in this study in- volve controlling agent to reach target point in a 2D space. In the first task, called "Catch- Point", the agent has control over its heading di- rection (continuous) and the option to either stop or move toward the target (binary variable). In the second task, known as "Hard-Move", the agent is equipped with actuators, and can decide to activate or deactivate each actuator (n binary ac- tions) and specify acceleration along each actuator (n continuous variables).
Target
Agent
Hard-Move
Agent
Catch-Point
2022; Fan al., 2019; Xiong et al., 2018). The HyAR algorithm has shown superiority over other Deep RI. techniques for high-dimensional hybrid action spaces. is important to acknowledge that TTPI assumes access the system dynamics and the reward function, whereas Deep RL techniques, in theory, are agnostic to the system model and implicitly address a more challenging problem than TTPI. However, many of these methods are data-inefficient and, like TTPI, assume access to simulator.
Evaluation: We evaluated our algorithm action spaces: the Catch-Point (CP) Problem and the Hare-Move (HM) problem. as proposed by Li al. (2022). The Catch-Point Problem has four states and an action space with one discrete and one continuous action. The Hard-Move problem has n actuators, resulting in a total of 2n action variables, with n binary and n continuous variables. Thus, this problem allows testing the scalability for high-dimensional action spaces by increasing
benchmark problems involving systems with hybrid
The results, as presented in Table provide strong evidence of TTP''s superior performance compared to the baseline method. TTPI demonstrates faster training times and generates highly performant policies. In contrast, the baseline method struggles with generalization and produces lower-quality solutions, particularly for the Hard-Move problem with number of actuators m > 12. This is attributed to TT-Cross accurately modeling the value functions by leveraging the system model and reward function, in fast manner and efficient policy retrieval using TTGO.
3.2 REAL ROBOT EXPERIMENTS
We demonstrate the effectiveness of proposed method for hybrid system control on planar pushing task with a face-switching mechanism (Xue et al., 2023) and involves discrete states and actions. The objective is push block with freedom in switching both the contact modes and faces.
7

---

Published as a conference paper at ICLR 2024
НРРО
PDQN
HyAR
TTPI
0.13
863
0.16
84%
0.15
92%
CP
0.5h
-0.01
1.6%
1.9h
10.05
1.6%
1:0002
1.4%
30s
100%
HM(8)
4
16
1.4h
-0.01
42%
88
2.1h
20.03
0.19
1.3%
8%
8h
1:0001
0.92
100%
850s
20.01
0.93
100%
0.92
12%
0.92
HM(12)
4
24
NA
NA
NA
NA
NA
NA
10h
946s
100%
1:0.05
1.5%
0.92
HM(16)
1743s
100%
=0.02
Table We used the success rate (S) for reaching the target position as one of the metrics. We note that the primary objective of both approaches, in the problems considered here, is to reach the goal in the shortest possible time or path. So as a second metric (μ), we calculate the square of the ratio between the length of the trajectory generated by each policy and the length of the shortest path for HM task. For CP task, μ is the inverse of the number of catch motions till reaching the goal. The table includes the training time (7') required to obtain the policy used for evaluation. The number of states is d and the number of actions is m.
It is modeled using 6 states and actions. The action includes discrete variable representing the index next contact face. Its underactuated and hybrid nature, coupled with multiple discrete contact modes, makes it difficult to design effective control strategies, and it has been a test-bed problem for the control hybrid systems. Previous approaches, such as mixed integer programming (Hogan Rodriguez, 2020) and hybrid Differential Dynamic Programming (Doshi et al., 2020), have struggled with the high computational cost required for solving the problem, which requires robust algorithms that can handle the complexity of hybrid systems with both continuous and discrete variables. Note that typically such a non-preiiee non-prehensile manipulation problem is formulated differently as continuous control (Ferrandis et al., 2023), due to lack of methodologies handle hybrid actions and is not representative hybrid control in robotics applications.
Our algorithm achieves robust performance: 100% success rate (reaching the goal) in both simulation and real- world experiments for this task. The experiments demonstrate successful reaching of the target position and orientation, even in the presence of additional weight and external disturbances, as shown in Fig. 3. This indicates the potential of TTPI for solving complex hybrid system control.
(a) Reaching
(b) Reaching w. additional weight
(c) Reaching w. disturbance
Figure 3: Pusher-slider system where the robot pushes object by contact switching. Three experiments were performed: The block being pushed towards the target as modeled (a), with additional weight the block leading to nonuniform friction distribution (b), and with external disturbance (c). The policy obtained from TTPI was robust to handle these scenarios.
4 LIMITATION
TTPI approximates the state-value and advantage function over the entire state-action space, resulting in highly generalizable policy. However, computational complexity and storage issues may arise when these functions not low-rank in the TT representation. For instance, systems involving highly agile movements like the acrobat (double pendulum swing-up) can lead to high-rank in the TT representation. Nonetheless, decreasing the time step At has been observed to reduce the rank
8

---

Published as a conference paper at ICLR 2024
of these functions which may enable the approach to handle such systems the expense of longer training time.
TTPI may be well-suited for commonly encountered systems with discontinuities and hybrid charac- teristics, such as manipulation and legged robotics. However, a drawback is its reliance on highly parallelized simulators. Hand-coding the system dynamics and reward function, demonstrated in this paper, may not be practical for more complex dynamics involving contact. While existing simu- lators like Mujoco and Raisim are not parallelizable and may slow down the process, the availability of recently introduced GPU-based simulators like NVIDIA Isaac Gym presents an opportunity to test the algorithm on more intricate applications.
Concerning scalability, although existing Deep RL techniques struggle to handle hybrid action space, they can cope well with high-dimensional state space (e.g., images as states). On the other hand, TTPI can handle high-dimensional hybrid actions and perform better compared to existing ADP methods, it may not be suitable for very high-dimensional state spaces. However, we could potentially enable our method to handle such high-dimensional problems by formulating instead of ADP or OC. In such cases, instead of TT-Cross, gradient-based methodologies (Novikov et al., 2017; Stoudenmire & Schwab, 2016) could be used to find the TT model of the value and advantage functions. We will investigate this in our future work.
approach an RL problem
5 RELATED WORK
In recent years, research has surged in the domain of optimal control for hybrid systems which involve mix of discrete and continuous state and action variables. Classical techniques, like Mixed-Integer Programming (MIP) (Marcucci & Tedrake, 2020), unify continuous and discrete variables a single optimization problem. Abstraction and reachability analysis methods (Alur et al., 2006) help adapt hybrid systems for traditional solvers. However, they often involve high computational complexity and are not suitable for real-time decision-making. This motivates the development of Approximate Dynamic Programming (ADP) techniques, which involve approximating value functions to alleviate computational burdens and handle -igeeniienionall settings.
The use of low-rank tensor approximation techniques for solving ADP was previously proposed in Horowitz et al. (2014), Gorodetsky et al. (2015), and Boyko al. (2021). Gorodetsky al. (2015) and Boyko et al. (2021), they proposed TT-based value iteration algorithm, where the TT was used to approximate the value function, and the policy was retrieved using Newton-type optimization technique based on the value function. This limits the application and speed of the algorithm, as the policy retrieval procedure demands the system dynamics and the reward function to be differentiable and the action space be continuous.
Some of the NN-based ADP for continuous state and action space have been proposed in fitted-Q iteration (Antos et al., 2007) and fitted-value iteration (Lutter et al., 2022). However, these methods have demonstrated their applicability only to systems with low dimensional systems and they have not been successful in handling hybrid action space. The NN-based ADP methods have been overshadowed by the rise of Deep RL as they have demonstrated scalability to problems with high dimensional state and action space. To overcome the issues in Deep RL for handling hybrid actions several improvements were proposed by Hausknecht & Stone (2016); Fu et al. (2019); Fan et al. (2019) and Li et al. (2022).
CONCLUSION
In this paper, we presented TTPI, an ADP algorithm that can handle hybrid action space. Through simulation experiments, we showed that the algorithm is superior to state-of-the-art algorithms for dealing with hybrid action spaces in terms of training time, generalization, and the quality of the policy. We demonstrated the robustness of the policy of TTPI through real-world experiments. The results demonstrate that our approach could be promising in robotics for solving challenging hybrid control tasks.
9

---

Published as a conference paper at ICLR 2024
A
APPENDICES
A.1
TT NN
Figure 4: The y-axis represents in log scale the ratio of approximation error in TT representation to that of the NN. The target function for approx- imation was chosen be GMM with various choices of mixture components & and dimension- ality d. The graph shows the superiority of TT modeling over NN for modeling such functions. For example, the graph shows that for = 20 and d 40, the error with TT is 10 times smaller than with NN. For k=5 and d=10, the error with TT is 10'000 times smaller than with NN.
10
d-10
d-20
d-30
d--40
Error ratio TT/NN
10"4
10
10
k=5
k=10 k=20
In this section, provide comprehensive analysis of the performance of Tensor Train (TT) compared to Neural Networks (NN) for function approximation. We employed a Gaussian Mixture Model (GMM) as representative target function, varying the number of mixture components (2 to 20) and dimensionality (2 to 40). The results in Figure 4 demonstrate that TT-Cross could accurately represent the target function in TT format, achieving orders of magnitude better accuracy compared to NN, and requiring significantly less time. Additionally, the nonparametric and unsupervised nature of TT-Crrss offers flexibility with minimal intervention, eliminating the need for careful selection, unlike the case of NN which requires careful hyperparameter tuning such as NN architecture, learning rate, and batch size. The superiority TT-Cross is due to the fact that the algortihm can directly query the function to evaluate trials, while exploiting the low-rank structure for the approximation. This motivates the use of TT for modeling value functions and advantage functions in Approximate Dynamic Programming (ADP).
In our experiment, TT-Cross was able find the TT representation of the GMM with less than 10-6 error as specified in TT-Cross in under 20 seconds for each test case, while NN took several minutes and had significantly higher error (often several orders of magnitude higher). Furthermore, NN required significant effort to tune the hyperparameters. whereas TT-Cross it is a non- nonn-arametric and unsupervised approach, was much easier to use. This is because TT-Cross finds the approximation by querying data (the function values at various points) intelligently (Savostyanov & Oseledets, 201 and exploits the structure in the function (i.e., low-rank or separability). can do so as TT-Cross directly takes the function be approximated as the input. On the other hand, NN takes a fixed set of samples from the function and does supervised learning to find the function approximation. We acknowledge that the approximation error in NN in our experiments could potentially be reduced by using more training data, and using more exhaustive search for best hyperparameters. However, this would increase the training time and manual effort.
Although NN is an established tool for supervised learning over datasets, it is inefficient, compared TT-Cross, when we need approximate known low-rank function accurately. Unlike TT-Cross, NN works with data collected from the function for the approximation and does not have feedback mechanism to query points from function during the approximation procedure. Thus, choosing NN as function approximation technique in ADP, where we need to repeatedly approximate value functions from the previous estimations, comes with a drawback. The software code for this comparison is provided in the supplementary material.
A.2 ADDITIONAL SIMULATION EXPERIMENTS
In addition to the benchmark problems on hybrid actions provided in the main section, we performed further experiments to evaluate the performance of our approach on some benchmark optimal control problems involving continuous states, including Point-mass control with obstacles, Cart-Pole Swing- up, and Box-pivoting. The video provided with the supplementary material shows the performance of the policy obtained by TTPI on these tasks.
10

---

Published as a conference paper at ICLR 2024
A.3 EXPERIMENTS WITH REAL ROBOT: PLANAR PUSHING TASK In this section, we discuss the performance our proposed method for a planar pushing task (Xue al., 2023). It is considered to be challenging in the field of model-baset planning and control, due to its underactuated and hybrid nature with several discrete contact modes.
The objective of the task is push block with the option of switching the face of the block to be pushed, as well as the contact mode used for pushing. We demonstrate that the proposed algorithms can achieve this task robustly in both simulation and the real world. A video of the experiments is provided in the supplementary material.
The state of the system is denoted [9. 4o co]_, where qs [sz Sy so] is the position and orientation of the block, qp = [Px Pyl is the position of end-effector, and c, {0, 1, 1, is the current contact face. The action is expressed as (v' c,]", where e [t,, vy] the velocity of the end-effector, and c, {0, 2, 3) is the next contact face. The system, therefore, has states and m = 3 control variables in total, including both continuous and discrete variables.
0.3
0.1
Figure 5: Simulation of the motion of the block under a policy from four different initial states. The colored trajectories represent the motion of the block to the target (g. [0 0 T) by means of contact mode and face switching.
ylm)
0.0
-0.1
-0.3
-0.3
-0.2
-0.1
0.0
0.1
0.2
0.3
We first trained the control policy in simulation based on the predefined motion equation. The continuous variables in state and action spaces discretized into 100 bins. The domain is set in the range from [-0.5m, -0.5m, -rj to [0.5m, 0.5m, T). with maximum velocity defined as 0.1 m/s. The accuracy of TT-cross is defined 10-3, The rank of the final value function was found to be 4 and the rank of the advantage function was 40. Each iteration of the VI procedure took about 10 seconds on average. To test the generalization capability of the policy, we randomly selected 1000 initialization points in the domain. A success rate of 100% was obtained in under 10 minutes of training. Fig. 5 shows the simulation results. The reward function is defined as
R( = -21g. (1 8(c. - cn)):
(10)
where qu represent the block pose, 8(ce cn) will return if c. cn (no face switching), otherwise. 0. Note that the flexibility offered by our method allows us to utilize such reward functions.
We then tested the trained policy on the real robot setup (Fig. 3), using 7-axis Franka Emika robot and RealSense D435 camera. The slider (r, = 6 cm) is a 3D 3D-printed prismatic object with PLA, lying on flat plywood surface, with an Aruco Marker on the top face. A wooden pusher (rp 0.5cm) is attached to the robot to move the object. The motion of the object is tracked by the camera 30 HZ., and the policy updated at 100 HZ, with a low-level Cartesian velocity controller (1000 HZ) actuating the robot.
Three experiments were conducted to assess the robustness of our policy: a) Reaching task: The robot pushes the slider from Qa [0.05m 0.16m 0J to the origin (Fig. 3a); b) Reaching with additional weight: The robot pushes the block from the same initialization as before, but with an additional weight, 3 times heavier than the block (Fig. 3b); e) Reaching with external disturbance: The same initialization like before, but with a significant external disturbance of quist = [0.1m 0.03m 90%] exerted by human (Fig. 3c).
11

---

Published as a conference paper at ICLR 2024
Table 2: Performance of three real-world experiments
Experiments
Wen/cm
yen/cm
0n/rrd
Reaching
-0.83
1.07
-0.06
Reaching with additional weight
2.89
-1.04
-0.01
Reaching with external disturbance
-4.78
-4.10
-0.04
The results of these experiments are shown in Table 2. The results show that in all experiments, the policy successfully reaches the final target in terms of both position and orientation. The error increases with the disturbance, while orientation errors remain less than 4 and position errors remain less than Sem even under significant disturbance. Experiment demonstrates that the policy is able to dynamically select the contact face based on the current state, evidenced by the change in contact face after a 90 rotation. This highlights the ability of our method to handle both continuous and discrete variables in hybrid systems.
A.4 CROSS APPROXIMATION METHOOSS
The popular methods to find the TT decomposition of tensor are TT-SVD (Oseledets, 2011), TT-DMRG (Dolgov& & Savostyanov, 2020), and TT-cross (Savostyanov Oseledets, 2011). TT-SVD and TT-DMRG, like matrix SVD, require the full tensor in memory to find the decomposition, and hence they are infeasible for higher-order tensors. TT-cross approximation is an extension of the matrix cross approximation technique for obtaining the TT decomposition of tensor. It is appealing for many practical problems as it approximates the given tensor with controlled accuracy, by evaluating only a small number of its elements and without having to compute and store the entire tensor in the memory. The method needs to compute only certain fibers of the original tensor at time and hence works in black-box fashion. In this section, we describe the matrix cross- coossapproximationn algorithm to provide an intuition about TT-Cross and we refer the readers to (Sozykin et al., 2022: Oseledets & Tyrtyshnikov, 2010; Savostyanov Oseledets, 2011) for more detail on how can be adapted to find the TT decomposition of higher-dimensiee
tensors using TT-cross.
Suppose we have a rank-r matrix P E R2 Using apos-approximattion (a.k.a. CUR decompo- sition or skeleton decomposition), this matrix can be exactly recovered using independent rows (given by the index vector é C (1...., nn ))) and r independent columns (given by the index vector 22 (1....,n2)
n2)) of the matrix P as
P $1
P...:
provided the intersection matrix P. Pay (called submatrix) is non-singular. Thus, the matrix P, which has n2 elements, can be reconstructed using only (n1 + n2 r)r of its elements (see Figure 6).
Now suppose we have noisy version of the matrix P = P + E with E < e and P is of low rank. For sufficiently small e, rank P) r so that the matrix P can be approximated with lower rank r (i.e., rank(P) R r). Then, the choice of the submatrix Poy.zz (or index vectors i1, i2) for the cross approximation requires several considerations. The maximum volume principle can be used in choosing the submatrix which states that the submatrix with maximum absolute value of the determinant is the optimal choice. If Peç ag is chosen to have the maximum volume, then by skeleton decomposition we have an approximation of the matrix P given by P = P P P This results in a quasi-optimal approximation
|P Pll < 1)2 (P))
where 0 (P) is the (r + 1)-th singular value of P (i.e., the approximation error in the best rank approximation in the spectral norm). Thus, we have an upper bound on the error incurred in the approximation which is slightly higher than the best rank r approximation Bockart-Young-Mishe theorem).
Finding the maximum volume submatrix is, however, an NP-hard problem. However, many heuristic algorithms that work well exist in practice by using submatrix with sufficiently large volume, trading off the approximation accuracy for the computation speed. One of the widely used methods is the MAXVOL algorithm (Goreinov et al., 2010) which can provide, given tall matrix P grxna (or Ra xr), the maximum volume submatrix Peç.a; E Rr The cross approximation algorithm uses the MAXVOL. algorithm in an iterative fashion to find the skeleton decomposition follows:
12

---

Published as a conference paper at ICLR 2024
1. Input: P x the approximation rank for the skeleton decomposition.
2. Find the columns index set iz and the row index set ž corresponding to the maximum volume submatrix.
2.1 Randomly choose r columns of the matrix P and repeat the following until conver- gence:
Use MAXVOI. to find r row indices i so that P 2g is the submatrix with maximum volume in .,a--
Use MAXVOL to find column indices ig so that Pa is the submatrix with maximum volume in P...:
3. Output: Using the column index set 22 and the row-index set eं corresponding to the maximum volume submatrix, we have the skeleton decomposition P..;; 2. Poj.-
In the above algorithm, during the iterations, the matrices P.. (or P...) might be singular. Thus, more practical implementation uses the pseudoinverses of these matrices. For details on practical implementation,
refer to Kishore Kumar & Schneider (2017). Note that, in the above algorithm, the input is only a function to evaluate the elements of the matrix P (i.e.. we do not need the whole matrix P computer memory).
Figure 6: For a given matrix P (top-left), suppose we know independent columns indexed by ig xr (12,1..... (...).......... i.e. P. i " and r indepen- dent rows indexed by éς = (i1,1....,f 1,,, i.e.,
Original
P.. E Rx*,, with their intersection Pay Rrxr being nonsingular. Then, by skeleton decom- position have P P... P.
Rank 3
If rank PP) = then = P (bottom row). For r rank (P) we obtain a quasi-optimal approxi- (middle row). The right figures show the rows and columns selected from the orig- inal matrix by the cross cross-approxinn approximation algorithm to find the skeleton decomposition.
mation, P
Rank
P
P.ne
P-1
Pue
A.5 REFINING TENSOR TRAIN MODEL
Suppose we have a model P defined on domain O2 Ozy X ... X Qr with discretization set X' x== {x = ( x²x') 2 E O2 & E (l,..., [2,]]. We can obtain a refined TT model P defined of the domain with âz > nı using interpolation of the TT cores in a fast manner. The cores of the corresponding TT model P defined over the refined discretization can be determined using P #t. = pk (Ix), , Vk E (l....,d), d), (f xa) E & using spline-based interpolation scheme as described in Section 2.6.
finer discretization X fx (zf (.'"
xxf) xt E Sox.
{1...., A&
This proves beneficial in specific applications where a coarse discretization employed during the learning phase to acquire the TT representation of a target function, which can be computationally intensive. During the inference phase, however, in some applications, the TT model might be required to be defined over finer discretization for more accurate results. For instance, in work, while modeling the advantage function using TT--rross we use a coarser discretization. However, the advantage function in TT format used for computing the policy using TTGO uses finer discretization. This ensures the attainment of more accurate optimum over action space.
A.6 TENSOR TRAIN DISTRIBUTION
Suppose we have a tensor P in TT format corresponding to a function with the discretization set X' of the domain Ωzz We can then construct the corresponding probability distribution that we call TT distribution,
p2 Pr(x) = Z
a X
(11)
13

---

Published as a conference paper at ICLR 2024
where Z is the corresponding normalization constant.
A.7 CONDITIONING TENSOR TRAIN DISTRIBUTION
Suppose we want to fix subset of variables in æ and find the corresponding conditional distribution of the remaining variables. Without loss of generality, let æ be segmented as a = (I (2) E U2z =
Dwy x Szz with 21 E aay C Rd, D2 22z C R i.e., 21 corresponds to the first d2 variables in æ. We are interested in finding the conditional distribution Pr(zz) (x1) the TT distribution given in (11).
Suppose 2 takes a particular value 2; = (Z),..., ,dd) ). We can obtain Pr(xz/ [1 = x2) by defining conditional TT model pa using TT model P
P = P (+e, #2); Va2 E E2z-
other words, the cores of p are then given by
(P x,: [II P Ri.
pd++1
Ve Puayis
2,
(12)
(P*))* = = -ptttd E (...... .2).
Given the above-defined conditional TT model, we can obtain the conditional distribution as (P
Pr(x22 xzi)
Vzz Swa.
(13)
Ze
In this work, Ti is the state variable, z2 is the action variable, and corresponds a transformed advantage function (see Section A.11).
A.8 SAMPLING FROM TENSOR TRAIN DISTRIBUTION Consider the discrete probability distribution given by (11). For the simplicity of the presentation, we assume as we will not require the normalization constant be known for sampling from the above distribution. Any probability distribution can be expressed as product of conditional distributions
Pr(zi...., Pri (21) (12()))))) Pra I4-1),
where
Ox(21 3kb
(r. Ik-1)
Tk-
(2)
xk-1)
is the conditional distribution defined using the marginals
Th (I
Σ Pr Pr(2i....,
18++1
Let do = Now, using the above definitions, we can generate samples æ ~ Pr by sampling from each of the conditional distributions in turn. Each conditional distribution is function of only one variable, and in the discrete case it a multinomial distribution with
Fk Pr. (#t/21.-. #1. 2k-1), Vk E (1....,d).
However, this process becomes computationally intensive during sampling 2x. as it necessitates the conditional distribution Prą. which, in turn, requires the evaluation of the summation several variables to find the marginal de.- Consequently, this approach incurs a computational cost that grows exponentially with the number of dimensions. Here, the TT format offers elegant solution by capitalizing on the separability of the function.
If Pr is TT distribution (see (11)) corresponding TT model P with the discretization set X and the cores (P- ..... Pd), we have
To (I 2t)) = Σ
Σ
P m:
k EEI.....,d4
F1+1
Zd
(14)
= =(P! m, P. su.
gh+l (p!...:" pp 2......)
14

---

Published as a conference paper at ICLR 2024
Algorithm 3 Sampling from TT distribution.
1: Input: TT Blocks P = (P), Pa)) corresponding to the distribution Pr, sample priority
E (0,1)
2: Output: . samples { )
N 1=1
from the distribution Pr (see (11))
3: gü+1
4: for k <- to 2 do
5:
g = Ex p.
i ou:
Bh+1 (P. ou.
6: end for
7: Φ1 t- 1 IEERNA R
8: for
1 to do
9:
n² = = Th. do
ghtl (Ph =' VaRk
10:
for for
11:
(*{+)) = [ (7, :) x (xx) ll T, Vrr
12: Sample o from the multinomial distribution pk
Lk+1(l, #x :) pk 2
14: end for
end for
where we can compute 8 efficiently in recursive manner
gk
... P. aa .
sk. .... pd #d.
sk:
Zd
(15)
Σ
Ph
gh+l
k (d......,
where gd+1 = 1. Alternatively, there exists a procedure called Tensor Train orthogonalization (Lee & Cichocki, 2018) which re-parameterizes the core tensors of P in TT format so that 3 is an identity matrix. This will eliminate the need for the computation given in (14). Thus, the TT format reduces the complicated multidimensional summation to evaluate σg into several one-dimensional summations. As the same summation terms appear over several conditionals Prx, we can obtain an efficient algorithm to sample from the TT distribution Pr which described in Algorithm 3. For more details, refer Dolgov et al. (2020).
A.9 TTGO: TENSOR TRAIN FOR GLOBAL OPTIMIZATION In this section, we propose efficient methodologies to find the maxima of TT-distribution given by (11). In the next sections we show how we can generalize it to find the optima arbitrary functions in TT format.
The methodology was proposed originally by Shetty et al. (2023) as stochastic procedure. was originally introduced to obtain multiple solutions and global optimality of TT distribution. Following this work, a deterministic version this approach was proposed by Chertkov et al. (2022). In the section, we further improve this deterministic version for applicability robotics for policy learning.
The idea behind TTGO is to leverage the Algorithm 3 to find the points corresponding to the high- density regions of the TT distribution. Recall that the sampling procedure in Algorithm 3 consists of repeated sampling of each dimension separately from multinomial distribution. We modify this by prioritizing the high-density values. To do this, instead of sampling N elements independently. we select the top N elements from the multinomial distribution Pl: at iteration k and we keep track of the history of the selected indices from the previous modes (k 1). i.e., we only retain top-N elements of Prę- This deterministic version of TTGO was proposed by Chertkov et al. (2022). We further improve this methodology to include smarter choices for top-N which improves the quality and diversity of the solution obtained. The idea is to give higher priority to the local maxima (peaks) of the multinomials involved in each iteration (i.e., Pry (Iyg ( zk-1)) 1).vk Vk E {1..... d} as described in Section A.8). In addition, introduce iterative procedure to improve the solution and scalability of the approach. This is sketched in Algorithm and we provide a fully parallel implementation in the software accompanying the paper.
15

---

Published as a conference paper at ICLR 2024
Algorithm 4 Deterministic TTGO
1: Input: TT Cores (Pi.... ..... Pd). Domain 2r = ,.., x)) : is E (I....,,y.) n)]]
2: Hyperparameters: N, Nimeeps E (l..... d),e default: K = 711, Nswesgs 1. 0.001
3: Output: Maxima x² = (zi,... 22) of the TT distribution given by P (see (11))
ge+1
5: for <- do do
6: 3 Em
end P Pk ske ghtl ph. Pk
8: Definition:
) (P)
pm
aa gm (p)
p
2
if (T" m
m- aim > x (xf+
20
mm sin t.).
m-
Va (1,-1)
OR (amm is discrete)
else i.c. lower weight n is not concave peak w.r.t. 2i
[c]
am
= q" (x] "r],..,,,,,
xm x"" (= "..."....
9: Initialize: D = {5,]] le E (1,....... min(N, ni) I E (1......u mih 22=f)2=((6)
10: Set Procx 0
11: for to Thwergs do
for m <- max (2, 8)
do
13:
D = ((x))
E (1. ..................... min(N, (ize(Dmm)) mm))
o (1,
*m $"1 ...., t
2 xm (x
}
(of p.., 1n 1==
14:
end for
(a (x.t.....*))) D
15:
x
(II,..., 2d)
16:
|m (x))
if p 2 Pmaz then
18:
Pmar + p x² +
19:
20:
end if
21:
DC =(,))
22:
end for
23:
Note: The associated software provides a highly parallel implementation of the above algorithm in PyTorch
where D are tensors.
A. FINDING OPTIMA ARBITRARY TENSOR TRAIN MODEL Given a TT model P. Algorithm 4 provides maxima arg max (P(x) (i.e. approximation to maximum
of the corresponding TT distribution given by (11)). To find the arg P(x:) using TTGO,
we first need to pre-process the TT model. We first find the maxima w.r.t the absolute value Fa arg max (a))) which can be done using TTGO with P. Next, we find a shifted TT model
P P - (xx) (using algebraic operations over TT model). Now we again use TTGO to find
Kt arg max (xx)). Ca and 2y are the two extrema (a maxima and a minima) of P. Thus,
Fmin arg min P(x) and Fmax arg max P(z). = ms}
m #o
A.11 NORMALIZING TENSOR TRAIN MODEL. Let Emin and Fmax be the minima and maxima of an arbitrary TT model P found using the methodology described in Section A. Let Pmin = (mmmi) and Pmax = PP(mmax). Then, we can
shift and scale the TT model P to obtain new TT model: P0 = Pruin + (P Pmii)
Pmmxx Puiin
Pmmax Paain
Then, (xx) (pmin, pmax), Vx Sp Note that Ømin and 2max are also the extrema of P. By specifying Pinin 0 and Pmax Proin can ensure that P. is non-negative.
16

---

Published as a conference paper at ICLR 2024
This is useful pre-processing step in practice to apply TTGO. To find the maxima of an arbitrary tensor P. we work with the corresponding non-negative TT model P. For instance, later in this chapter, a typical use case of TTGO in robotics is to find x = arg max P(Za, Fa) 2t
describe
where P Pat v:a) could be negative. So, we first find the normalized TT model P and then 27 arg
P(x,, zd) can be found using TTGO for various 2t on the conditioned TT model max max md P ma (as defined in Section A.7) So, unless otherwise specified, assume the TT model P is normalized to be non-negative while using TTGO.
A.12 POLICY COMPUTATION USING TTGO
Recall that TTPI represents the advantage function in TT format obtained using TT-Cross. The policy at each iteration given by TT)) arg max A(s, a) is computed using TTGO. Suppose A denotes
the TT representation of the advantage function. In practice, we first normalize the TT model A to get a normalized TT model Á as described in Section A. Then given any state 8, we can compute the policy π T()) = arg max A(s, a) using TTGO. More specifically, it is done by applying TTGO on the conditioned TT model A as defined in Section 12.
REFERENCES
Rajeev Alur, Thao Dang, and Franjo Ivančić. Predicate abstraction for reachability analysis of hybrid systems. ACM Transactions on Embedded Computing Systems (TECS), 5(1):152-19)) 199, 2006.
András Antos, Csaba Szepesvári, and Rémi Munos. Fitted Q-iteration in continuous action-space MDPs. Advances in neural information processing systems, 2007.
Dimitri Bertsekas. Dynamic programming and optimal control. Athena scientific, 2012.
Alexey I. Boyko, I. Oseledets, and Gonzalo Ferrer. TT-QI: Faster value iteration in tensor train format for stochastic optimal control. Computational Mathematics and Mathematical Physics, 61: 836 066-846,22 2021.
Andrei Chertkov, Gleb Ryzhakov, Georgii Novikov, and Ivan Oseledets. Optimization of functions given in the tensor train format. arXiv:2209. 14808, 2022.
Andrzej Cichocki, Namgil Lee, Ivan V. Oseledets, Anh Huy Phan, Qibin Zhao, and Danilo P. Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part 1 low-rank tensor decompositions. Foundations and Trends in Machine Learning, 2:249-429, 2016.
S. Dolgov, Karim Anaya-Izquierdo, C. Fox, and R. Scheichl. Approximation and sampling of multivariate probability distributions in the tensor train decomposition. Statistics and Computing. 30:603-625, 2020.
Sergey Dolgov and Dmitry Savostyanov. Parallel cross interpolation for high- precision calculation of dich-dimensional integrals. Computer Physics Communications, 246: 106619 2020.
Neel Doshi, Francois R Hogan, and Alberto Rodriguez. Hybrid differential dynamic programming for planar manipulation primitives. In IEEE International Conference on Robotics and Automation (ICRA), pp. 7765, 2020.
Zhou Fan, Ruilong Su, Weinan Zhang, and Yong Yu. Hybrid actor-critic reinforcement learning in parameterized action space. In International Joint Conference on Artificial Intelligence, 2019.
Juan Del Aguila Ferrandis, Joao Pousa De Moura, and Sethu Vijayakumar. Nonprehensile planar manipulation through reinforcement learning with multimodal categorical exploratio... In IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), 2023.
Haotian Fu, Hongyao Tang, Jianye Hao, Zihan Lei, Yingfeng Chen, and Changjie Fan. Deep multi- agent reinforcement learning with discrete-continuos hybrid action spaces. In Proceedings of the 28th International Joint Conference Artificial Intelligence (IJCAI), 2019.
17

---

Published as a conference paper at ICLR 2024
Sergei A. Goreinov, I. Oseledets, Dmitry V. Savostyanov, Eugene E. Tyrtyshnikov, and Nickolai Zamarashkin. How to find a good submatrix. Matrix Methods: Theory, Algorithms And Applications: Dedicated to the Memory of Gene Golub, pp. 247-256. World Scientific, 2010.
Alex Gorodetsky, Sertac Karaman, and Youssef Marzouk. Efficient high-dimensional stochastic optimal motion control using tensor-train decomposition. In Proc. Robolics: Science and Systems (R:SS), pp. 1-8, July 2015.
Lars Grasedyck, Daniel Kressner, and Christine Tobler. A literature survey of low-rank tensor approximation techniques. MAMM--iiteilungenn, 36(1)753-7 2013.
Zhao-Yo Yu Han, Jun Wang, Heng Fan, Lei Wang, and Pan Zhang. Unsupervised generative modeling using matrix product states. Phys. Rev. X, 8:031012, Jul 2018.
Matthew J. Hausknecht and Peter Stone. Deep reinforcement learning in parameterized action space. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference Learning Representations (ICLR), 2016.
Francois Robert Hogan and Alberto Rodriguez. Feedback control of the pusher-slider system: A story of hybrid and underactuated contact dynamics. Algorithmii Foundations of Robotics XII: Proceedings of the Twelfth Workshop the Algorithmic Foundations of Robotics, pp. 800-815. Springer, 2020.
Matanya B. Horowitz, Anil Damle, and Joel W. Burdick. Linear Hamilton Jacobi Bellman equations in high dimensions. IEEE Conference on Decision and Control (CDC), pp. 5880-5887, 2014.
N Kishore Kumar and Jan Schneider. Literature survey on low rank approximation of matrices. Linear and Multilinear Algebra, 65(11))2212-22244 2017.
T. Kolda and B. Bader. Tensor decompositions and applications. SIAM Review, 51(3):555-500 2009.
Namgil Lee and Andrzej Cichocki. Fundamental tensor operations for large-scale data analysis using tensor network formats. Multidimennsional Systems and Signal Processing, 29(3):921-99) 260,, 2018.
Boyan Li, Hongyao Tang, Yan Zheng. Jianye Hao, Pengyi Li, Zhen Wang. Zhaopeng Meng, and LI Wang. HyAR: Addressing coscrete-continuuus action reinforcement learning via hybrid action representation. In International Conference Learning Representations (ICLR), 2022.
Michael Lutter, Boris Belousov, Shie Mannor, Dieter Fox, Animesh Garg, and Jan Peters. Continuous- time fitted value iteration for robust policies. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Tobia Marcucci and Russ Tedrake. Warm start of mixed-integer programs for model predictive control of hybrid systems. IEEE Transactions on Automatic Control, 66(6):2433 2448, 2020.
Alexander Novikov, Mikhail Trofimov, and Ivan V. Oseledets. Exponential machines. In International
Conference on Learning Representations (ICLR), 2017.
Georgii Sergeevich Novikov, Maxim Panov, and I. Oscledets. Tensor-train density estimation. In Uncertainty in Artificial Intelligence, pp. 1321-1331, 2021.
Ivan Oseledets and Eugene Tyrtyshnikov. TT-cross approximation for multidimensional arrays. Linear Algebra and its Applications, 432(1):70-88,, 2010.
Ivan V. Oseledets, Tensor-train decomposition. SIAM Journal on Scientifiic Computing, 33:2295-2317. 2011.
Dmitry V. Savostyanov and Ivan V. Oseledets. Fast adaptive interpolation of multi-dimennionall arrays in tensor train format. The 2011 International Workshop on Multidimensionall (nD) Systems, pp. 1-8, 2011.
S. Shetty, T. Lembono, T. Löw, and S. Calinon. Tensor trains for global optimization problems in robotics. International Journal of Robotics Research (IJRR), 2023.
18

---

Published as a conference paper at ICLR 2024
Nikos D. Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos E. Papalexakis. and Christos Faloutsos. Tensor decomposition for signal processing and machine learning. IEEE Transactions Signal Processing, 65:3551-3582, 2017.
Konstantin Sozykin, Andrei Chertkov, Roman Schutski, Anh-Huy Phan, Andrzej S CICHOCKI, and Ivan Oseledets. Ttopt: A maximum volume quantized tensor train-based optimization and its application reinforcement learning. Advances in Neural Information Processing Systems, 35: 26052-26065, 2022.
Edwin Miles Stoudenmire and David J. Schwab. Supervised learning with tensor networks. In Neural Information Processing Systems, 2016.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. JEEE Transactions Neural Networks, (6:285-286, 2005.
Jiechao Xiong, Qing Wang. Zhuoran Yang. Peng Sun, Lei Han, Yang Zheng, Haobo Fu, Tong Zhang, Ji Liu, and Han Liu. Parametrized deep Q-networks learning: Reinforcement learning with discrete-continuuus hybrid action space. arXiv:/8/0.066394 2018.
Teng Xue, Hakan Girgin, Teguh Santoso Lembono, and Sylvain Calinon. Demonstration guided optimal control for long-term non-preten non-prehensile planar manipulation. In Proc. IEEE Intl Conf. Robotics and Automation (ICRA), pp. 4999-5005, 2023.
19


Reviews:
[{"review_id": "aDyjBTK0OT", "reviewer": "Reviewer_BNgN", "summary": "This paper develops a method to solve approximate dynamic programming with Tensor Train (TT) representation, which is a compressed tensor to discretely approximate a function. The authors first give a compact and quite neat backgrounds for TT representation and associated operations with TT. The main contribution is a policy iteration algorithm, where the authors replace traditional continuous function approximators (such as using neural network) with TT representations. The authors show the performance of the algorithm using a toy examples in comparison with baseline methods. The method has also been demonstrated in real world robot for a manipulation task.", "questions": "Since in the introduction the authors mentioned RL, I think it would be interesting to discuss the potential of the methods into \"model-free\" settings.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The authors did a good job presenting the necessary background of TT and its associated operations (such as decomposition, rounding, TT-Cross, and TT-go).  I think the authors have fairly discussed the limitation of the method.", "weaknesses": "1. My main concern of the paper is the experiment, which is quite limited and there are many remaining questions. Particularly, there are many hyperparameters, it is expected to have ablation study of showing the performance of the method versus the hyperparameters, such as accuracy $\\epsilon $ of TT representation, the max TT rank $r_{max}$, discretization resolutions of the state-action spaces.... \n\n2. As a reader to implement the algorithm, I wanted to see a straightforward illustration between the running time of the algorithm and dimensions of the state/action spaces of the system, or directly give an overall complexity of the algorithm for one policy iteration.\n\n3. Since the majority of the paper is about the background of TT (previous work), I think the main contribution, which is TTPI algorithm, needs more explanation, including its parallel implementation, which seems a key for applicability of the algorithm. For example, why we need a TT-round operation for the value function in line 8?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "yNWpGhF9n5", "reviewer": "Reviewer_ntHE", "summary": "The paper tackles the problem of controlling dynamic systems that involve both continuous and discrete actions (termed \"hybrid actions\") is challenging in robotics.  The innovative aspect of the authors' solution is the use of the Tensor Train (TT) format, a method to approximate functions with a low-rank tensor. The TT format allows the authors to approximate two crucial components:\nState-value function: Represents the value of being in a particular state.\nAdvantage function: Indicates how much better taking a certain action is compared to others.", "questions": "Tensor operations, especially in high-dimensional spaces, can sometimes introduce numerical instability. How does the TTPI algorithm ensure numerical stability, especially in long-horizon problems?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces TTPI, an Approximate Dynamic Programming (ADP) algorithm designed for optimal control. The method leverages Tensor Train (TT) format to address challenges in hybrid system control in robotics.\nTraditional control algorithms face problems with systems with non-smooth dynamics and discontinuous reward functions. Existing solutions also often assume differentiability in the system dynamics, which may not always hold.\n\nThe paper introduces TTPI, an Approximate Dynamic Programming (ADP) algorithm designed for optimal control. The method leverages the Tensor Train (TT) format to address challenges in hybrid system control in robotics. The experiments show TTPI outperforming other state-of-the-art algorithms in training speed and control performance. A real-world robotics experiment further demonstrates the effectiveness and robustness of this method.", "weaknesses": "As the authors themselves mentioned, hand-coding the dynamics in the experiments is very hard to do for complex environments.\n\nTTPI approximates state-value and advantage functions over the entire state-action space, which can result in computational and storage challenges, especially if these functions are not low-rank in the TT representation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "6ifxyDSyy1", "reviewer": "Reviewer_3rMV", "summary": "The authors use the Tensor Train (TT) model to approximate the state-value function $V$ and advantage function $A$ during policy iteration while solving optimal control problem. At each step of the policy iteration this functions is being rebuilt using well-known _TT-cross_ algorithm which adaptively queries a certain number of points to the black-box model function to be approximated. In addition, policy $\\pi$ is built on these iterations using the known TTGO algorithm, which searches for the maximum of the TT-tensor based on sampling from it. The performance of the algorithm was tested on several model and real robot examples, showing its superiority on them. The distinctive feature of the algorithm is the use of hybrid actions.", "questions": "- did you use ideas from _opitma_tt_ (paper Chertkov et al. (2022)) which utilize _top-k_ scheme and thus more accurate?\n- what are the typical TT-ranks for double pendulum swing-up in the case of small $\\Delta t$ when the model does work?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is very well structured, the authors have described not only the method and practical application, but also the limitations.\n\n- There is code, which allows for reproducible experimentation. In the supplementary materials there is a video with demonstrations of both synthetic experiments and real experiments with a mechanical arm.\n\n- Numerical and in-situ experiments show the superiority of this method.\n\n\n- Potentially, this approach is applicable to rather multi-dimensional problems (with large dimensionality of stats or actions) since the TT construction overcomes the curse of dimensionality, and the authors use TT-format compression for all possible functions.\n\n- The approach presented in the paper allows for serious expansion in both quality and time. The authors have identified some of these potential opportunities in the paper.", "weaknesses": "I found no significant weaknesses in this article.\nAs a small remark, the use of a uniform grid in section 2.6 could be pointed out, while it might be more accurate to use, for example, a Chebyshev grid.\nAlso there are no theoretical estimates (ranks, for example) and no discussion when we expect small TT-ranks. I.e., can we say in advance, without iterating, that the method works. However, this is a general problem of methods using a low-parameter tensor representation.\n\nThe paper cited as arXiv (Sozykin et al., 2022) is now officially published: https://proceedings.neurips.cc/paper_files/paper/2022/hash/a730abbcd6cf4a371ca9545db5922442-Abstract-Conference.html\n\nmaybe typo: p4 \"decomposition equation 5\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "bEDma7HexF", "reviewer": "Reviewer_F3ze", "summary": "The paper proposes a method for solving optimal control problems (assuming a correct dynamics model is available) with mixed continuous and discrete state variables, using an efficient representation of the value function of the problem based on a set of low-dimensional tensors, in a tensor-train (TT) format. An empirical evaluation demonstrates the effectiveness of the proposed method on several control problems of moderate complexity.", "questions": "How well will the algorithm perform on a somewhat higher dimensional problem, for example a 6 or 12 dimensions?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "One of the main strength of the paper lies in the efficient way of computing the optimal action from the tensor-based representation of the value function. It is based on an explicit representation of the advantage function, again in tensor-train format, and the use of the TT-Cross algorithm for an efficient TT approximation of the advantage function after it has been computed by means of a Bellman back-up.\n\nAnother strength of the paper is the rather impressive verification of the algorithm on control problem with six continuous state variables and a single discrete variable, on a real robot.", "weaknesses": "Although the example on the real robot is very impressive, the examples in simulation are less so. Four-dimensional state space is not that high, barely beyond what can be represented with a look-up table on modern computers. (10^8 cells will take around 400MB of FP numbers.) The authors clearly state that their algorithm is not meant to approximate value functions on very high-dimensional state spaces, such as images, but most robotics applications on 6 degree of freedom robots have 12-dimensional state space, so this is perhaps the dimensionality of highest interest. \n\nSome claims are not entirely justified. For example, the authors say \"OC is synonymous with ADP\". There is some overlap, but the two fields are hardly the same. Many OC algorithms, including the celebrated LQR and LQG algorithms, are based on basic DP, nothing approximate about it. \n\nFurthermore, the authors say that MuJoCo is not parallelizable. I cannot agree with this, MuJoCo has always been easy to parallelize on multiple CPU cores, and the latest release of MuJoCo, 3.0.0, can run on GPUs and TPUs. True, it came out after ICLR papers were submitted, but please reconsider this claim.\n\nThe authors also mention \"the need for differentiability of the system dynamics and reward function which is a common assumption in the existing ADP algorithms\". This is probably not entirely correct, as many ADP algorithms simply sample the system dynamics. \n\nFurthermore, the authors often use the phrase \"policy retrieval\", implying that somehow the policy has been lost. Suggest replacing with \"policy computation\" or \"policy evaluation\".\n\nSome minor typos:\nAppendix A.3: citation missing in the first sentence \nSame place: \"n=6 states\" -> \"n=6 state\" (completely changes the meaning)\n\"HZ\" -> \"Hz\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)