# A Generic Solver for Unconstrained Control Problems
with Integral Functional Objectives

Shih-Hao Tseng Shih-Hao Tseng is with the Division of Engineering and Applied
Science, California Institute of Technology, Pasadena, CA 91125, USA. Email:
<EMAIL_ADDRESS>
###### Abstract

We present a generic solver for unconstrained control problems (UCPs) whose
objectives take the form of an integral functional of the controllers. The
solver generalizes and improves upon the algorithm in [1] for the
Witsenhausen’s counterexample, which provides the best-known results. In
essence, we show that minimizing the objective implies minimizing the marginal
cost functions almost everywhere, and we perform the latter task pointwisely
by the adaptive minimization technique, which speeds up the computation. We
implement single-threaded and parallelized versions of the proposed algorithm.
Our implementation runs $30\times$ faster than the algorithm in [1] on the
Witsenhausen’s counterexample, and we demonstrate the applicability of the
solver and discuss the possible generalization to constrained problems through
two more examples.

##  I Introduction

In this work, we focus on the unconstrained control problem (UCP) with the
objective

$\displaystyle\min\ \mathcal{J}[U]$

where $U=\left\\{u_{0}(y_{0}),u_{1}(y_{1}),\dots,u_{M-1}(y_{M-1})\right\\}$ is
the set of controllers $u_{m}:\mathbb{R}\to\mathbb{R}$. We assume that the
objective functional $\mathcal{J}[U]$ can be expressed as

$\displaystyle\mathcal{J}[U]=\int L_{m}(u_{m}(y_{m}),y_{m})\
dy_{m}+\mathcal{R}_{m}[U_{-m}]$ (1)

for all $m=0,\cdots,M-1$ (in other words, the functional can be expanded with
respect to each $m$), where $L_{m}:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$
and $\mathcal{R}_{m}[U_{-m}]$ is the _residual functional_ depending only on
the controllers other than $u_{m}$. Although omitted, we remark that $L_{m}$
might also depend on $U_{-m}$ and the decomposition of $L_{m}$ and
$\mathcal{R}_{m}$ is not necessarily unique.

Finding the optimal controller of a control problem is a daunting task, even
when the problem imposes no constraints. The traditional approach to a control
problem is to analyze its structure and conclude some useful properties that
would help find the optimal controller. However, as demonstrated by the famous
Witsenhausen’s counterexample [2], preferred properties, such as linearity,
does not hold in general. As a result, deriving the optimal controller becomes
craftsmanship relying on keen observations.

Fortunately, we often need a near-optimal controller rather than an exact
optimal one in practice. There are two approaches, the analytical and the
numerical, to design a near-optimal controller. The former approach examines
some specific controller structure based on the problem characteristics.
Again, the performance of the design highly depends on the sophisticated
understanding of the problem. On the other hand, the numerical approach
develops techniques to approximate the problem and obtain good approximations
of the optimal controllers. Correspondingly, the main challenges lie on
computation efficiency and approximation quality.

It used to be the computation-demanding nature of the numerical methods which
impedes the adoption. But luckily, the advancing technologies in the past
decades have hugely reshaped the research landscape: Cheaper computation
resources and parallelization techniques facilitate the development of image
classification [3], machine learning [4, 5], and genomics processing [6].
Increased computation power not only grants us higher efficiency but also
enables finer sampling granularity and potentially better approximation
quality. Therefore, we argue that numerical methods have great potential in
the upcoming computation-rich era.

Although numerical methods could potentially compute faster with plenty of
computation resources, its effectiveness plays a central role in getting
closer to the optimum. Blindly adopting numerical methods can be ineffective.
Accordingly, it is critical to ask how to design numerical methods that are
effective for general problems, in particular, for general UCPs.

Our approach to tackling general UCPs evolves from the algorithm proposed for
the Witsenhausen’s counterexample in 2017 [1]. The algorithm in [1]
outperforms all previous attempts on the well-known Witsenhausen’s
counterexample (e.g., [7, 8, 9]), and its mechanism does not depend on the
property of the given objective functional. Although the algorithm finds the
controllers that result in the record-low cost, it is computationally
demanding and requires a special math tool called calculus of variation.

###  I-A Contribution and Organization

We examine UCP and provide a generic algorithm to find a near-optimal
controller numerically. The proposed algorithm generalizes the algorithm in
[1] with the following improvements: First, it presents a new angle viewing
the local Nash minimizing phase in the algorithm in [1] which does not involve
calculus of variation. In summary, our analysis reveals that UCP leads to a
per-point marginal cost optimization problem, and the two methods used in the
algorithm in [1], local Nash minimizing and local denoising, approach the
problem using different candidate sets. We also apply the adaptive
minimization technique to speed up the convergence significantly. Furthermore,
our proposed algorithm adopts a unified termination criterion applicable to
arbitrary UCPs.

We then implement a generic solver based on the proposed algorithm in C++ and
demonstrated that it converges $3\times$ faster than the algorithm in [1] on
Witsenhausen’s counterexample. Since the proposed algorithm is parallelizable,
we enhance the single-threaded C++ implementation using NVIDIA CUDA and
observe another $10\times$ computation speed up. We also demonstrate how the
solver works on the zero-delay source-channel coding problem and inventory
control problem. And we open source the tool for future research.

The paper is organized as follows. We first provide a brief overview of the
algorithm in [1] in Section II. Section III introduces the ideas of marginal
cost functions, local update, partial exhaustion, and adaptive minimization.
Those ideas contribute to the design of our solver. We then implement the
solver and examine its performance improvement in Section IV. In Section V, we
demonstrate that how we can use the solver to approach different problems.
Finally, we conclude the paper in Section VI.

###  I-B Notation

By convention, we denote the state by $x$, control by $u$, observation by $y$,
and disturbance by $w$. Let $\mathbb{E}_{A}$ be the expected value with
respect to random variable $A$. We omit $A$ when the expectation is taken with
respect to all random variables. We denote by
$A\sim\mathcal{N}(\mu,\sigma^{2})$ a Gaussian random variable $A$ with mean
$\mu$ and variance $\sigma^{2}$ and by $A\sim\mathcal{U}(a,b)$ a uniform
random variable distributed over $[a,b]$. Given a number $M$, we slightly
abuse the notation to denote $m=0,\dots,M-1$ by $m\in M$. For a multivariate
function $F(a,b)$, we introduce the shorthand notation
$F^{\prime}(a,b)=\frac{\partial F(a,b)}{\partial a}$ to denote the partial
derivative with respect to the first variable.

##  II Existing Algorithm and its Limitation

We first explain the algorithm in [1], which attains the state-of-the-art best
results for Witsenhausen’s counterexample, in Section II-A. We then discuss
the limitations of the algorithm in Section II-B.

###  II-A Basic Structure

In [1], Witsenhausen’s counterexample is deemed an optimization problem
minimizing a given functional. To obtain the best controllers, the algorithm
in [1] introduces two main components: local Nash minimizers and local
denoising.

####  II-A1 Local Nash Minimizers

[1] shows that an optimal controller must be a local Nash minimizer. Using
calculus of variation, the first order condition (FOC) and the second order
condition (SOC)

$\displaystyle\frac{\delta\mathcal{J}[U]}{\delta
u_{m}}(y_{m})=0,\quad\frac{\partial}{\partial
u_{m}}\frac{\delta\mathcal{J}[U]}{\delta u_{m}}(y_{m})\geq 0$

are then derived for local Nash minimizers. Combining FOC and SOC, the
algorithm in [1] repeats revised Newton’s method to seek for a local Nash
minimizer.

####  II-A2 Local Denoising

The most important observation given by [1] is that finding local Nash
minimizers numerically would land in a “noisy” controller. As a result, [1]
introduces the idea of “denoising,” i.e., for each $u_{m}$, we denoise for all
$y_{m}$ by

$\displaystyle u_{m}(y_{m})\leftarrow$ $\displaystyle\
\operatorname*{argmin}\limits_{u_{m}(y):y\in
B_{r}(y_{m})}C_{m}(u_{m}(y),y_{m}),$

where $B_{r}(a)$ is a ball centering at $a$ with radius $r$.

###  II-B Limitations

Although the algorithm in [1] is demonstrated effective for Witsenhausen’s
counterexample and it is applicable to other similar problems such as
inventory control, there are still few issues left by [1]. First, albeit a
universal approach to finding local Nash minimizers, calculus of variation is
not a simple idea/operation for the people who know little about functional
analysis. For local denoising, [1] obtains functions $C_{m}$ by observation.
It would be more rigorous to have a standard procedure to derive $C_{m}$.
Meanwhile, despite its great performance in terms of the final cost it
achieves, the algorithm runs slow in practice. And it is not clear how the
termination criterion used in [1] can be easily generalized for arbitrary
problems.

##  III Generic Algorithm Design

In this section, we study UCP and illustrate how to overcome the limitations
stated in Section II-B so that we can improve the ideas in [1] to solve UCPs.

###  III-A Marginal Cost Functions

We start the analysis with Lemma 1, which is a necessary condition for optimal
$U$, followed by the derivation of the _marginal cost function_ $C_{m}$.

######  Lemma 1.

If $U$ minimizes $\mathcal{J}$, we have

$\displaystyle
u_{m}(y_{m})=\operatorname*{argmin}\limits_{u\in\mathbb{R}}L_{m}(u,y_{m})$

almost everywhere for all $m\in M$.

The lemma can be derived from (1) and the derivation is straightforward.

Lemma 1 relates the optimal $u_{m}(y_{m})$ with $L_{m}(u,y_{m})$. However, a
UCP is usually specified by $\mathcal{J}$ and its decomposition to
$L_{m}(u,y_{m})$ is in general not unique. We would prefer to base our solver
on Lemma 1 with respect to a more deterministic expression than $L_{m}$.
Therefore, we derive the _marginal cost function_ $C_{m}$ as follows.

From (1), we know

$\displaystyle
L_{m}(u_{m}(y_{m}),y_{m})=\frac{\partial\mathcal{J}[U]}{\partial
y_{m}}-\frac{\partial\mathcal{R}_{m}[U_{-m}]}{\partial y_{m}}$

which implies that

$\displaystyle
L_{m}(u,y_{m})=\left.\left(\frac{\partial\mathcal{J}[U]}{\partial
y_{m}}-\frac{\partial\mathcal{R}_{m}[U_{-m}]}{\partial
y_{m}}\right)\right|_{u_{m}(y_{m})=u}.$

Substitute it into Lemma 1, we have

$\displaystyle u_{m}(y_{m})=$ $\displaystyle\
\operatorname*{argmin}\limits_{u\in\mathbb{R}}\left.\left(\frac{\partial\mathcal{J}[U]}{\partial
y_{m}}-\frac{\partial\mathcal{R}_{m}[U_{-m}]}{\partial
y_{m}}\right)\right|_{u_{m}(y_{m})=u}$ $\displaystyle=$ $\displaystyle\
\operatorname*{argmin}\limits_{u\in\mathbb{R}}\left.\frac{\partial\mathcal{J}[U]}{\partial
y_{m}}\right|_{u_{m}(y_{m})=u}$

because $\mathcal{R}_{m}[U_{-m}]$ does not depend on $u$. Thus, we define the
_marginal cost function_ $C_{m}$ for each $m\in M$ by

$\displaystyle C_{m}(u,y_{m})=\left.\frac{\partial\mathcal{J}[U]}{\partial
y_{m}}\right|_{u_{m}(y_{m})=u}$

and we can rephrase Lemma 1 as

######  Corollary 1.

If $U$ minimizes $\mathcal{J}$, we have

$\displaystyle
u_{m}(y_{m})=\operatorname*{argmin}\limits_{u\in\mathbb{R}}C_{m}(u,y_{m})$

almost everywhere for all $m\in M$.

Now, once we have the objective $\mathcal{J}$ specified, $C_{m}$ can be
derived using simple partial derivation. Actually, the definition of $C_{m}$
also matches with the observation in [1].

###  III-B Local Update and Partial Exhaustion

Corollary 1 is not only a necessary constraint but also a way to improve a
non-optimal controller. Essentially, we can always improve a non-optimal
solution by

$\displaystyle
u_{m}(y_{m})\leftarrow\operatorname*{argmin}\limits_{u\in\mathbb{R}}C_{m}(u,y_{m}).$

To do so, we need to find the minimizer of $C_{m}(u,y_{m})$.

To find the minimizer, the most effective method is to exhaust all possible
$u\in\mathbb{R}$ and choose the best one. A full exhaustion is rarely
practical as the computational cost would be intolerable. Instead, we would
prefer computationally economic methods, such as _local update_ and _partial
exhaustion_.

Local update methods include gradient descent, Newton’s method, and their
variations. Those methods rely on local information at $y_{m}$, such as
derivatives, to update $u_{m}$. Partial exhaustion takes a different approach.
It avoids the heavy computational load in a full exhaustion by searching
within only a subset of candidate values.

Not surprisingly, these two methods correspond to the two main components in
the algorithm in [1]. Since

$\displaystyle\frac{\delta\mathcal{J}[U]}{\delta u_{m}}(y_{m})=$
$\displaystyle\ C_{m}^{\prime}(u_{m}(y_{m}),y_{m}),$
$\displaystyle\frac{\partial}{\partial
u_{m}}\frac{\delta\mathcal{J}[U]}{\delta u_{m}}(y_{m})=$ $\displaystyle\
C_{m}^{\prime\prime}(u_{m}(y_{m}),y_{m}),$

finding local Nash minimizers using the revised Newton’s method in [1] is
equivalent to minimizing the function $C_{m}(u,y_{m})$ at each $y_{m}$ by a
revised Newton’s method.

$\left\\{u:u\in B_{r}(u_{m}(y_{m}))\right\\}$

(a) Local update

$\left\\{u_{m}(y):y\in B_{r}(y_{m})\right\\}$

(b) Partial exhaustion

Figure 1: The candidate sets used in different techniques are marked by shaded
areas. We depict the function $u_{m}$ by the thick blue line and mark the
range of $B_{r}$ by red dashed lines. The candidate set can be disjoint in
partial exhaustion when $u_{m}(y_{m})$ is discontinuous.

On the other hand, local denoising is a partial exhaustion method that
searches within the candidate set

$\displaystyle\left\\{u_{m}(y):y\in B_{r}(y_{m})\right\\}$ (2)

to minimize $C_{m}(u,y_{m})$. This is an important feature of the algorithm in
[1]: It searches over the domain instead of the range of the function $u_{m}$.
Usually, a partial exhaustion method searches the argument value locally,
i.e., it considers the candidate set

$\displaystyle\left\\{u:u\in B_{r}(u_{m}(y_{m}))\right\\}.$

Such a partial exhaustion method plays a similar role as a local update method
since they both try to update

$\displaystyle u_{m}(y_{m})\leftarrow$ $\displaystyle\
\operatorname*{argmin}\limits_{u:u\in B_{r}(u_{m}(y_{m}))}C_{m}(u,y_{m})$

for some small $r$. As a result, we do not benefit much from combining the
methods together. However, (2) can be a disconnected set when $u_{m}$ is
noncontinuous as in Fig. 1, which allows searching and “leaping” to another
region.

###  III-C Adaptive Minimization

Both local update and partial exhaustion methods are adopted alternatively in
the algorithm in [1]: In each repetition round, it denoises the controllers
after repeating the revised Newton’s method several times. This hybrid
strategy converges to the best-known results, but it progresses quite slowly.
The reason is that the two methods improve $\mathcal{J}$ in different ways and
one may be more effective than the other at different searching phase.

(a) The algorithm in [1] runs local update $19$ times and performs $1$ partial
exhaustion per round. Partial exhaustion is more effective than local update.

(b) Adaptive minimization allocates $20$ iterations in each round to the
methods according to the improvement in the last round. As such, both methods
improve $\mathcal{J}$ comparably.

(c) Comparison of the overall improvement. Adaptive minimization outperforms
the algorithm in [1] significantly.

Figure 2: The improvement of the objective functional $\mathcal{J}$ in the
Witsenhausen’s counterexample for each method. Each round has $20$ iterations.

In Fig. 22(a), we consider the Witsenhausen’s counterexample as in [1] and
plot the average $\mathcal{J}$ value improvement of the local update method
(revised Newton’s method) and the partial exhaustion method (denoising) for a
series of repetition rounds, each round consisting of $19$ local update
iterations and $1$ partial exhaustion iteration. Fig. 22(a) shows that partial
exhaustion performs much better than local update, but local update runs much
more times than partial exhaustion. As a result, the overall improvement at
each round is low as in Fig. 22(c).

To improve the efficiency, we introduce _adaptive minimization_. The basic
idea is that we will adapt the number of iterations according to the
performance of the method. The more effective method gets more iterations to
run. Fixing the total iterations to be $20$ per round, we perform adaptive
minimization and Fig. 22(b) shows that the average improvements of the two
methods are comparable. Furthermore, the overall improvement is boosted by
adaptive minimization as shown in Fig. 22(c).

###  III-D Generic Algorithm

We combine the methods described in Section III-B and Section III-C to
construct Algorithm 1 for UCP. In summary, Algorithm 1 approximates the
controllers $U$ by step functions over a given sample range. Then, it
adaptively minimizes $\mathcal{J}[U]$ using local update and partial
exhaustion methods. Adaptive minimization is repeated until some precision
factor is met. The whole procedure can be partitioned into five main parts,
and we give more detailed descriptions below.

10: Number of iterations per round $N$ and

precision $p\geq 0$.

1: Initialize controllers $U$.

2: $\mathcal{J}_{c}\leftarrow\mathcal{J}[U]$. $\cdot$ Initial objective
value..

3: $I_{L}\leftarrow p$, $I_{P}\leftarrow p$. $\cdot$ Initial improvements..

4: $N_{L}\leftarrow\left\lfloor\frac{N}{2}\right\rfloor$, $N_{P}\leftarrow
N-N_{L}$. $\cdot$ Initial iterations..

5: while $I_{L}+I_{P}>p$ do$\cdot$ Main loop

6: for $N_{L}$ iterations do

7: for $m=0$ to $M-1$ do

8: LocalUpdate($u_{m}$)

9: end for

10: end for

211: $\mathcal{J}_{c}\leftarrow\mathcal{J}[U]$,
$I_{L}\leftarrow|I_{L}-\mathcal{J}_{c}|$.

$\cdot$ Get local update improvement..

12: for $N_{P}$ iterations do

13: for $m=0$ to $M-1$ do

14: PartialExhaustion($u_{m}$)

15: end for

16: end for

317: $\mathcal{J}_{c}\leftarrow\mathcal{J}[U]$,
$I_{P}\leftarrow|I_{P}-\mathcal{J}_{c}|$.

$\cdot$ Get partial exhaustion improvement..

18:
$N_{L}=\min\left\\{\max\left\\{\left\lfloor\frac{I_{L}N}{I_{L}+I_{P}}\right\rfloor,1\right\\},N-1\right\\}$,
$N_{P}\leftarrow N-N_{L}$. $\cdot$ Adaptive minimization..

19: end while

Algorithm 1 Generic Solver

####  III-D1 Initialization (line 1 – 4)

Given some sampling range $[a,b]\subseteq\mathbb{R}$ and number of samples
$d$, we create a linearly spaced vector $\mathbb{Y}\in\mathbb{R}^{d}$ spanning
over $[a,b]$ as the domain. Each controller $u_{m}$ is then approximated by a
function mapping $\mathbb{Y}$ to $\mathbb{R}$. As suggested in [1], we
initialize $u_{m}$ by an identity map:

$\displaystyle u_{m}(y_{m})\leftarrow y_{m}\quad\text{for all}\quad
y_{m}\in\mathbb{Y}.$

Also, we initialize the current objective value $\mathcal{J}_{c}$, improvement
$I_{L},I_{P}$, and iterations $N_{L},N_{P}$ for adaptive minimization. We use
subscript $L$ to denote the variable for local update and subscript $P$ for
partial exhaustion.

####  III-D2 Main Loop (line 5)

We repeat adaptive minimization in the main loop, and we adopt a unified
termination criterion: The loop terminates when the overall improvement in the
current round is smaller than the precision $p$. This criterion improves upon
the one adopted in [1] as it is valid regardless of the objective
$\mathcal{J}$.

####  III-D3 Local Update (line 6 – 1)

In this phase, we aim to solve

$\displaystyle u_{m}(y_{m})\leftarrow$ $\displaystyle\
\operatorname*{argmin}\limits_{u:u\in B_{r}(u_{m}(y_{m}))}C_{m}(u,y_{m})$

for all $y_{m}\in\mathbb{Y}$ using some local update methods.

In our implementation, we adopt a modified Newton’s method slightly different
from the one in [1]: We only apply Newton’s method

$\displaystyle u_{m}(y_{m})\leftarrow
u_{m}(y_{m})-\frac{C_{m}^{\prime}(u_{m}(y_{m}),y_{m})}{C_{m}^{\prime\prime}(u_{m}(y_{m}),y_{m})}$

when

$\displaystyle C_{m}^{\prime\prime}(u_{m}(y_{m}),y_{m})>0$

which implies a local minimum. Otherwise, we apply simple gradient method

$\displaystyle u_{m}(y_{m})\leftarrow u_{m}(y_{m})-\tau
C_{m}^{\prime}(u_{m}(y_{m}),y_{m})$

where $\tau$ is the given step size.

####  III-D4 Partial Exhaustion (line 12 – 1)

We perform partial exhaustion based on the sampled candidate set (2):

$\displaystyle u_{m}(y_{m})\leftarrow$ $\displaystyle\
\operatorname*{argmin}\limits_{u_{m}(y):y\in
B_{r}(y_{m})\cap\mathbb{Y}}C_{m}(u_{m}(y),y_{m})$

for all $y_{m}\in\mathbb{Y}$. Essentially, it is equivalent to the local
denoising procedure with denoising radius $r$.

####  III-D5 Adaptive Minimization (line 18)

We perform a per-round adaptive minimization by updating the iterations
according to the improvements in the last round. Starting with fair sharing as
in line 1, we calculate the improvements gained from each of the methods by
line 1 and 1. In line 18, we allocate the $N$ iterations in the next round
proportional to the contribution of each method while ensuring each method
will be run at least once.

##  IV Performance

To demonstrate the performance, we implement Algorithm 1 in two different
versions: the single-threaded solver in C++ (denoted by _Single_) and the
parallelized one in NVIDIA CUDA (denoted by _Parallel_). The solvers are open
sourced at [10]. The solvers are run under the number of iterations per round
$N=20$ and the precision $p=10^{-10}$.

We compare our solver with the algorithm in [1] [1] on the Witsenhausen’s
counterexample, for which the formulation is deferred to Section V-A, under
the parameters $k=0.2$ and $\sigma=5$.

For fair comparison, we impose the same termination criterion and total
iterations per round for the algorithm in [1]: It performs local Nash
minimizing $19$ times followed by $1$ local denoising. All experiments are run
on a desktop with Intel Xeon W-2145 (CPU), NVIDIA Quadro P1000 (GPU), and
Samsung 970 EVO NVMe M.2 (SSD).

###  IV-A Parallelization

To reduce the computation time, we examine Algorithm 1 and identify the parts
that can be parallelized.

In both the local update and partial exhaustion phases, we revise $u_{m}$ one
at a time, which may change $C_{m^{\prime}}$ for some $m^{\prime}\in
M,m^{\prime}\neq m$. As a result, such a dependency prevents the computation
being done in parallel. On the other hand, updating $u_{m}(y_{m})$ does not
affect $C_{m}$, and hence the calculation for each $y_{m}\in\mathbb{Y}$ can be
parallelized to reduce the computation time.

###  IV-B Computation Time

Figure 3: Comparison of the convergence time among different methods. the
algorithm in [1] converges faster in the beginning but it converges much
slower when approaching to the optimum. On the contrary, both single-threaded
and parallelized versions of Algorithm 1 converge much faster towards the
optimum.

Fig. 3 shows how fast the solvers and the algorithm in [1] converges along the
computation time under $14000$ sample points. the algorithm in [1] converges
quickly at the beginning since it computes $u_{1}$ directly through a closed
form expression. On the contrary, Algorithm 1 does not utilize any closed form
expression. It simply searches for $u_{0}$ and $u_{1}$ using local update and
partial exhaustion. Although the algorithm in [1] is more effective in
computing $u_{1}$, adaptive minimization allows Algorithm 1 to select and use
the more effective method. As a result, the single-threaded version converges
slower at the beginning, but it improves $\mathcal{J}$ much more effectively
than the algorithm in [1] when getting closer to the limit. After
parallelization, the convergence speed is further improved by $10\times$,
shifting the curve to the left in Fig. 3.

###  IV-C Scalability

Figure 4: Algorithm 1 scales much better than the algorithm in [1]. The
parallelized version generates the controllers $30\times$ faster than the
algorithm in [1].

Another property we examine is scalability. Scalability is important for a
numerical method as it implies how precise the approximation can be and how
large the problem the solver can handle. To demonstrate the scalability, we
vary the number of sample points for each controller and measure the
computation time needed before reaching the required precision level. In Fig.
4, the single-threaded solver runs about $3\times$ faster than the algorithm
in [1]. After parallelization, the computation time is further reduced by
$10\times$, and hence it enjoys $30\times$ performance improvement over the
algorithm in [1].

##  V Examples

We apply our solver to three different examples: Witsenhausen’s counterexample
(Section V-A), zero-delay source-channel coding (Section V-B), and inventory
control (Section V-C). Since inventory control problem imposes additional
constraints on the controllers, we discuss how our solver might be generated
for the problem with constraints.

###  V-A Witsenhausen’s Counterexample

Figure 5: Controllers for Witsenhausen’s counterexample ($k=0.2,\sigma=5$),
$\mathcal{J}[U]=0.166897$.

Witsenhausen’s counterexample [2] aims to minimize the objective

$\displaystyle\min\
\mathcal{J}[U]=\mathbb{E}\\!\left[k^{2}u_{0}(y_{0})^{2}+x_{2}^{2}\right]$

subject to the system dynamic

$\displaystyle x_{1}=$ $\displaystyle\ x_{0}+u_{0}(y_{0}),$ $\displaystyle\
\quad\ y_{0}=$ $\displaystyle\ x_{0},$ $\displaystyle x_{2}=$ $\displaystyle\
x_{1}-u_{1}(y_{1}),$ $\displaystyle\ \quad\ y_{1}=$ $\displaystyle\ x_{1}+w,$

where $x_{0}\sim\mathcal{N}(0,\sigma^{2})$ and $w\sim\mathcal{N}(0,1)$.

We use our solver to find controllers in Fig. 5. The result is very close to
the best-known controller in [1].

###  V-B Zero-Delay Source-Channel Coding

Figure 6: Controllers for zero-delay source-channel coding problem
($\lambda=2$), $\mathcal{J}[U]=0.890756$.

The zero-delay source-channel coding problem [11] has the objective

$\displaystyle\min\ \mathcal{J}[U]=\mathbb{E}\\!\left[\lambda
u_{0}(x_{0})^{2}+(u_{1}(x_{1})-x_{0})^{2}\right]$

and the system dynamic

$\displaystyle y_{0}=x_{0},\quad x_{1}=u_{0}(y_{0})+w,\quad y_{1}=x_{1},$

where $x_{0}\sim\mathcal{N}(0,1)$ and $w\sim\mathcal{U}(-1,1)$.

Fig. 6 shows the non-linear controllers found by our solver.

###  V-C Inventory Control and Constrained Controller

Figure 7: Controllers for the inventory control problem using the same setting
as in [1].

The inventory control problem has the objective

$\displaystyle\min\ \mathcal{J}[U]=\mathbb{E}\\!\left[\sum\limits_{m=0}^{M}\xi
u_{m}(x_{m})+\gamma(x_{m+1})\right]$

where $\gamma$ is some cost function attaining the minimum at $0$.

The system dynamic is

$\displaystyle y_{m}=x_{m},\quad x_{m+1}=x_{m}+u_{m}(x_{m})-w_{m},$

where $x_{0}\sim\mathcal{U}(-1,1)$ and $w_{m}\sim\mathcal{U}(-1,1)$ for all
$m\in M$.

The inventory control problem imposes an additional constraint: $u_{m}\geq 0$.
We can enforce the constraint by performing
$u_{m}\leftarrow\max\left\\{0,u_{m}\right\\}$ after each local update and
partial exhaustion. With the same settings as in [1], our solver finds the
same controllers as in Fig. 7. It is reported in [1] that this enforcement
successfully finds the optimal controllers. Therefore, we conjecture that it
is possible to generalize this generic UCP solver for the problems with
constraints by projecting the result back to the feasible region after each
local update and partial exhaustion.

##  VI Conclusion

The paper examines the unconstrained control problems and proposes an
effective generic solver which can serve as the benchmark for the future UCP
research. On the other hand, a lot of control problems do impose constraints
on either the states of the controllers. As a result, it would be of interest
to generalize the solver to constrained control problems.

## References

  * [1] S.-H. Tseng and A. Tang, “A local search algorithm for the Witsenhausen’s counterexample,” in _Proc. IEEE CDC_ , dec 2017.
  * [2] H. S. Witsenhausen, “A counterexample in stochastic optimum control,” _SIAM J. Control_ , vol. 6, no. 1, pp. 131–147, 1968.
  * [3] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “ImageNet classification with deep convolutional neural networks,” in _Proc. NIPS_ , 2012, pp. 1097–1105.
  * [4] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in _Proc. NIPS_ , 2014, pp. 2672–2680.
  * [5] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng, “Tensorflow: A system for large-scale machine learning,” in _Proc. USENIX OSDI_ , 2016, pp. 265–283.
  * [6] Y. Turakhia, G. Bejerano, and W. J. Dally, “Darwin: A genomics co-processor provides up to 15,000$times$ acceleration on long read assembly,” in _Proc. ASPLOS_. ACM, 2018, pp. 199–213.
  * [7] N. Li, J. R. Marden, and J. S. Shamma, “Learning approaches to the Witsenhausen counterexample from a view of potential games,” in _Proc. IEEE CDC_ , 2009, pp. 157–162.
  * [8] J. Karlsson, A. Gattami, T. J. Oechtering, and M. Skoglund, “Iterative source-channel coding approach to Witsenhausen’s counterexample,” in _Proc. IEEE ACC_ , 2011, pp. 5348–5353.
  * [9] M. Mehmetoglu, E. Akyol, and K. Rose, “A deterministic annealing approach to Witsenhausen’s counterexample,” in _Proc. IEEE ISIT_ , 2014, pp. 3032–3036.
  * [10] UCP solver. [Online]. Available: https://github.com/shih-hao-tseng/UCP-Solver
  * [11] E. Akyol, K. B. Viswanatha, K. Rose, and T. A. Ramstad, “On zero-delay source-channel coding,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 12, pp. 7473–7489, 2014.


#  Speeding up reinforcement learning by combining attention and agency
features

Berkay Demirel
University Pompeu Fabra
Barcelona, Spain Martí Sánchez-Fibla
University Pompeu Fabra
Barcelona, Spain Corresponding Author: Technology Department, Universitat
Pompeu Fabra, Carrer de Roc Boronat 138, 08018 Barcelona, Spain. E-mail:
<EMAIL_ADDRESS>
###### Abstract

When playing video-games we immediately detect which entity we control and we
center the attention towards it to focus the learning and reduce its
dimensionality. Reinforcement Learning (RL) has been able to deal with big
state spaces, including states derived from pixel images in Atari games, but
the learning is slow, depends on the brute force mapping from the global state
to the action values (Q-function), thus its performance is severely affected
by the dimensionality of the state and cannot be transferred to other games or
other parts of the same game. We propose different transformations of the
input state that combine attention and agency detection mechanisms which both
have been addressed separately in RL but not together to our knowledge. We
propose and benchmark different architectures including both global and local
agency centered versions of the state and also including summaries of the
surroundings. Results suggest that even a redundant global-local state network
can learn faster than the global alone. Summarized versions of the state look
promising to achieve input-size independence learning.

_K_ eywords Deep Reinforcement Learning, Agency, Attention

##  1 Introduction

When playing a video-game for the first time, we can quickly discern which
entities are we in control (and when we are in control of those entities) by
pressing buttons randomly, and we can direct attention to the immediate
surroundings of those entities to reduce the state space dimensionality of the
learning. Even in games with first person view we constantly direct attention
towards what we can have an effect on. Decomposing the perceived state into
different entities is fundamental for generalization and transfer learning
[2]. Attentional mechanisms are crucial in the brain to direct learning
abilities [8]. Reinforcement Learning (RL) has been able to deal with big
state spaces, including states derived from pixel level images (i.e. Deep Q
Network, DQN, learning to play Atari games [6]) thanks to the usage of Deep
Convolutional Neural Networks to approximate the mapping of states and actions
to future reward. The performance of RL algorithms like DQN is severely
affected by the size/dimensionality of the input state spaces, which does not
seem to be the case for human play performance. We believe that this input
size independence may be achieved by the combination of visual attention [5]
and agency detection mechanisms [11, 1, 10] to deliver an agent-centered view
of the state to the RL algorithm. We argue and prove experimentally that it is
beneficial to center the state where the agent can cause immediate effects.
Thus we are proposing to deliver a first person view of the state centered
where the actions cause effects and where the agent has direct agency. This
agency-centered state can have higher resolution in the center and lower in
the surroundings and can include a summary of the important features that are
out of reach. Some computer games (like Doom, Quake, Obstacle Tower Challenge)
or robotics applications (like the one we describe in [9]) are naturally first
person view (or close to it) and we think that they can still benefit from our
approach as a first person view can be centered towards the focus of agency,
the part of the view in which the agent can have the maximum effect. In first
person shooter games like Doom, the target of the gun could be a possible
candidate; in a robotics hand object manipulation this would be the case of
the hand.

We propose and benchmark different architectures including both global and
local agency centered versions of the state and also including summaries of
the surroundings. Results suggest that even a redundant global local state
network can learn faster than the global alone.

##  2 Methods

We model the environment by a Markov Decision Process (MDP). An MDP is a tuple
$\langle S,A,P,R,\gamma\rangle$ where $S$ is the state of states, $A$ the set
of actions, $P$ the transition probability distribution $P:S\times A\times
S\rightarrow[0,1]$ satisfying $\sum_{s^{\prime}}P(s^{\prime}|s,a)=1$, $R$ the
expected reward function for every state and action $R:S\times
A\rightarrow\mathbb{R}$ and $\gamma$ the discount factor of the return (reward
obtained from state $s$ and discounted geometrically by $gamma$):
$G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+...$. The aim of Reinforcement
Learning (RL) is to learn an optimal policy that maps states to actions
$\pi:S\rightarrow A$ such that future expected reward is maximized:
$\mathbb{E}_{\pi}[G_{t}|S_{t}=s]$ being $S_{t}$ the state at time $t$.

RL algorithms like Q-Learning solve the problem by estimating the so-called
action-value function $Q:S\times A\rightarrow\mathbb{R}$ from which an optimal
policy can be obtained by ”greedyfication”:
$\pi^{*}(s)=\mathrm{argmax}_{a}Q(s,a)$

When the state space is high dimensional as in the case of Atari games where a
state $s\in\mathbb{R}^{210x160x3}$ a Deep Convolutional Neural Network (DCNN)
is used to approximate $Q$ as in the case of DQN algorithm in which also a
technique named experience replay is used to update the DQN function in
batches of stored experience so to make the samples as much as independent and
identically distributed (i.i.d) as possible.

###  2.1 Setup

We use a modified version of the Fruit Collection environment [12]. It
consists of an 11 by 11 grid world, the outer most layer consisting of walls,
effectively limiting the positions where the agent can move to 81. The agent
as well as 5 fruits are initialized to randomly distinct positions on the
grid. The agent has 4 available actions to move in the 4 cardinal directions:
up, down, left and right. The environment used in ”pixel mode”, has what we
call a global state $s^{global}\in\mathbb{R}^{11x11x3}$, 3 channels sized 11 x
11 corresponding to agent location, fruit locations and walls respectively.
Each time the agent enters a position where a fruit is present, it is rewarded
with +1 and the fruit disappears. An episode ends when all fruits are
collected or after 80 steps, whichever comes first. This pixel mode allows the
use of convolutions as it keeps the spatial relationship between features,
while keeping the training required for feature recognition to a minimum by
one hot encoding of features on different layers.

###  2.2 Agency Detection

From the described global state $s^{global}\in\mathbb{R}^{11x11x3}$ one could
compute the coordinates of the agent that is controlled by the available
actions. There exist different studies that deal with the problem of
identifying controllable features of the state [11]. In [1] this is called
learning agency. In [10] the controllable features of the state are assessed
by computing correlations of the motor actions into the optical flow effects
of the different visual features. In the following we are going to assume that
we know the coordinates in the global state of the agent that is controlled by
the available actions and that is what we mean when we say we assume knowledge
of agency.

###  2.3 State Transformations

We describe in the following the different operations that we use to transform
the global state into an agent-centered view and reduced local view around the
agent (see Figure 1).

The first operation, that we call centering, enables to center the state at a
certain position $i,j$ of the matrix (this position will be the one of the
agent). We consider two possible centering modes: rolling $f^{center}_{roll}$
and padding $f^{center}_{pad}$. When centering by rolling the roll operation
is used $f^{roll}_{x,y}$ which does a circular rolling of the rows (by $x$
positions) and columns (by $y$ positions) without losing information (as if
the environment had a torus topology in which the extremes are connected).
Centering to position $i,j$ can be achieved by rolling $(nrows+1)/2-i$ the
rows of each channel and rolling $(ncols+1)/2-j$ the columns of each channel
(being $nrows$ and $ncols$ the number of rows and columns respectively of the
matrix). As $s^{global}\in\mathbb{R}^{11x11x3}$ centering by rolling is:
$f^{center}_{roll}(s)=f^{roll}_{6-i,6-j}(s)$.

Centering can also be achieved with padding: each matrix is padded with zeros
adding rows and columns,
$f^{center}_{pad}(s)=f^{sub}_{11x11}(f^{roll}_{i,j}(f^{pad}_{16x16}(s)))$. In
the case of centering with padding some information might be lost when the
agent is near the limits of the environment.

Once centered a sub-matrix can be extracted so as to discard the outer rows
and cols of the matrix thus extracting what we call the local state,
considering the immediate surroundings of the agent that is controlled by the
actions. For example the local agent centered view with padding would be:
$s^{local}=f^{sub}_{3x3}(f^{center}_{pad}(s))$.

Finally we describe the ”summary transformations” of the state. Consider the
padded centered state as made up of progressively larger layers surrounding
the agent like an onion. We eliminate iteratively each external layer by
taking the mean of the weighted sum into the inner layers. This is realized in
multiple steps. First, the value of each point in the outermost layer of the
state matrix is multiplied by a constant of 0.9. This makes sure that the
outer layers are weighted less as they are far from the immediate reach of the
agent. Secondly, the mean of each point and it’s two immediate neighbours is
taken and added to the value of the point that is directly one layer below it
in the state matrix. This operation is repeated until a 3x3 matrix is obtained
in the case of $s^{summary}_{3x3}=f^{summary}_{3x3}(f^{center}_{pad}(s))$ or
stopping earlier and having the summary values surround the local state space
to create a 5x5 matrix:
$s^{summary}_{5x5}=f^{summary}_{5x5}(f^{center}_{pad}(s))$. The ”summary
transformations” have the nice property of being local (while preserving a
weak form of total observability) and independent of the size of the
environment. ”Summary transformations” also depend heavily on the existence of
a one-hot encoded feature map, similar to our state representations as the RGB
colour values could not be meaningfully summarized with this approach.

The final four important state transformations that will be used in the
following for the learning architectures are:

  * •

Global state: the intact $s^{global}\in\mathbb{R}^{11x11x3}$ (see Figure 1a).

  * •

Global centered-roll state: $f^{center}_{roll}(s)$ (See Figure 1d).

  * •

Global centered-padded state: $f^{center}_{pad}(s)$ (See Figure 1e).

  * •

Local state: $s^{local}=f^{sub}_{3x3}(f^{center}_{pad}(s))$ (See Figure 1f).

  * •

Summary states: $s^{summary}_{3x3}$ and $s^{summary}_{5x5}$ (See Figure 1g and
1h).

Figure 1: State Transformations. a),b) Global state
$s^{global}\in\mathbb{R}^{11x11x3}$ and its different 3 channels: walls (grey
squares), fruits (in blue) and the agent position (white square). c) padded
state result of $f^{pad}_{16x16}(s)$ operation in which all channels are
filled with zeros in the surroundings. d) Centering with wrap around result of
$f^{center}_{roll}(s)=f^{roll}_{x,y}(s)$ operation. e) Centering operation
after padding
$f^{center}_{pad}(s)=f^{sub}_{11x11}(f^{roll}_{x,y}(f^{pad}_{16x16}(s)))$.
Some information might be lost and the state becomes partially observable. f)
Local state extracted from the centered state version:
$s^{local}_{pad}=f^{sub}_{3x3}(f^{center}_{pad}(s))$. g),h) Summarized
versions of the local state: $s^{summary}_{3x3}$ and $s^{summary}_{5x5}$

###  2.4 Agent and Architectures

The agent implements a state of the art reinforcement learning algorithm that
in our case we have selected Deep Q Learning, DQN [6] with prioritized
experience replay. As mentioned previously, in DQN, the Q-function is
approximated using neural networks. The network consists of an input layer
corresponding to each variation’s global state size: 3x11x11 for the no
centering architectures and 2x11x11 for both centering with padding and
centering with wrap around architectures. The first hidden layer is a
convolutional layer consisting of 12 kernels of size 3x3, with a stride of 1
and rectified linear unit (relu) activation function. The second hidden layer
is another convolutional layer of 16 kernels of size 3x3, with a stride of 1
and relu activation function. On the third layer, the output of the last layer
is flattened before passing densely to 16 nodes with a relu activation
function. The output layer consists of 4 nodes, each corresponding to a
directional movement action. Huber loss is used as the loss function and Adam
with a learning rate of 0.0002 as the optimizer.

The target network weights are updated every step using Polyak averaging with
a tau of 0.0005. Each agent is trained for 800 episodes with a discount factor
of 0.95. Epsilon decays linearly from 1 at the $1^{st}$ episode to the final
value of 0.05 at $750^{th}$ episode. The experience replay buffer size is
10000 for the architectures that use the global state, while it is 2400 for
the architectures that utilize the local state. The training starts after the
buffer is filled by a random policy agent. At each step a batch of size 32 is
selected from the buffer with a chance proportional to the size of the TD-
error with a guarantee that every experience will be replayed at least once.
The weights of the experiences are inversely proportional to their TD-error to
offset the selection bias, and updated for each experience whenever they are
replayed.

###  2.5 Global Architecture

This architecture consists of 3 variations:

$\bullet$

No centering variation assumes no agency knowledge and as such the 3x11x11
state returned from the environment is directly passed on to the agent without
any transformations.

$\bullet$

Centering with padding variation assumes agency knowledge. This variation pads
the environment with 0s before centering it around the agent. The layer
representing the agent position is not required because of the agent-centered
view and is dropped. The agent is passed a 2x11x11 state. This variation also
turns the problem from a Markov Decision Process to Partially Observable
Markov Decision Process as the Markov property does hold because of the loss
of information in the transformation.

$\bullet$

Centering with wrap around variation assumes agency knowledge. This variations
wraps the environment around itself from both axes. The layer representing the
agent position is not required because of the agent-centered view and is
dropped. The agent is passed a 2x11x11 state. This variation does not turn the
problem into a POMDP as the Markov property still holds because there is no
information loss in the transformation.

Figure 2: Learning Architectures. a) Global architecture which takes as input
the global state $s^{global}$. The network is a Deep Convolutional Neural
Network (DCNN). b) Two separate networks have as input $s^{local}$ and
$s^{global}$ respectively. c) A single network receives as input both
$s^{local}$ and $s^{global}$. d) A single network receives the summarized
version of the state $s^{summary}$.

###  2.6 Global and Local Architecture

In this architecture, the global state is decomposed into 2 parts: one local
and one global. While the global one is the same as the one used in the global
architecture, the local state is the 3x3 grid surrounding the agent denoted as
$s^{local}_{pad}$ in section 2.3. The agent consists of 2 different networks:
the global network and the local network, taking as input $s^{local}$ and
$s^{global}$ respectively. Action selection is mediated by a simple
conditional rule: if a feature exists in the local state, the action is
selected according to the local network, otherwise, the global network is used
for action selection. This rule is selected for it’s simplicity, effectively
making the agent rely on the global network for navigation while using the
local network for reacting to the local stimuli. As it does not utilize the
global state when there is a feature in the local space, it is not expected to
be optimal but rather serve as a test for the performance of the agent when
different networks for different state spaces are used. More complex action
selection schemes such as a confidence measures can also be utilized.

$\bullet$

No centering: This variation is similar to the same variation of the global
architecture with the addition of a decomposed local state centered around the
agent. The global state is a matrix of size 3x11x11, while the local state is
2x3x3.

$\bullet$

Centering with padding: The global state is centered around the agent, the
agent position channel dropped and the necessary parts padded with 0s. The
global state is a matrix of size 2x11x11, while the local state is 2x3x3.

$\bullet$

Centering with wrapping around: The environment is wrapped around itself from
both axes, the global state is centered around the agent and the agent
position channel dropped. The global state is a matrix of size 2x11x11, while
the local state is 2x3x3.

###  2.7 Global and Local Integrated Architecture

This architecture differs from the previous Global and Local network by
getting rid of the rule for network selection and integrating both $s^{local}$
and $s^{global}$ into the same network in a decomposed manner. The global
network is modified by adding a secondary input layer that takes the local 3
by 3 state around the agent. This local state $s^{local}$ is convolved by 6
kernels with size 2x2 with a single stride and flattened afterwards. This
flattened local state is concatenated with the flattened global state before
connecting to the dense layer of 16 nodes and passed to the output layer. This
allows the network to learn when to rely on the local state, as the local
state space would be empty when no features are detected and thus the output
of the network would solely rely on the global state. Similar to the global
and local architecture, this architecture has 3 variations involving how the
global state is transformed before passing along to the agent:

$\bullet$

No centering variation involves passing the global state to the agent without
any transformation. The global state is a matrix of size 3x11x11, while the
local state is a matrix of size 2x3x3.

$\bullet$

Centering with padding involves passing the global state to the agent by
centering the view on the agent, dropping the agent location channel and
padding the necessary parts with 0s. As a result, the global state is a matrix
of size 2x11x11, while the local state is a matrix of size 2x3x3.

$\bullet$

Centering with wrapping around involves wrapping the global state on both axes
around itself before centering it on the agent and dropping the agent location
channel. The global state is a matrix of size 2x11x11, while the local state
is of size 2x3x3.

###  2.8 Summary Architecture

This architecture utilizes the local summary state space transformation that
we call $s^{summary}$ in section 2.3. The state is reduced to a lower
dimensionality state by doing a weighted sum of the outer layers of the state
towards the inner ones. The architectures takes an input a reduced version of
the global state that maintains a weak total observability.

$\bullet$

3x3 Summary: In this variation the global environment is collapsed onto itself
until a 3 by 3 grid surrounding the agent remains.

$\bullet$

5x5 Summary: In this variation the 3 by 3 layer surrounding the agent is kept,
while the environment is collapsed around this local view, creating a 5 by 5
grid.

##  3 Results

Figure 3: Running mean rewards for all the variations

Figure 3 shows the mean reward obtained by each variation and architectures
(we use a running window average 50 episodes). In the first subplot,
variations with centering show a much higher learning performance from the
beginning and converge much earlier than the global no centering variation.
This can be attributed not only to the more compact state space representation
by getting rid of the agent location channel, but also to the location
invariance resulting from centering the state. The compact state space
representation is more informative and as a result less examples and training
time is needed for convergence. There is no difference in the learning
performance of the padded centering and wrap around centering variations.
Although this lack of difference in performance is unintuitive given that the
padded centering variation is partially observable, it can be attributed to
the simplicity of the environment and the task.

Figure 4: Comparison of the best performing architectures

The results of the global and local architecture are similar to the global
architecture, showing higher performance for the centering variations compared
to the no centering variation. The global and local integrated architecture,
similar to all other architectures show increased performance of centered
variations, with a lower and less stable learning performance for the no
centering variation.

The results of the summary architecture show that the 5x5 summary variation
has a small but significant learning advantage compared to the 3x3 summary
variation. Although the state representation is larger in the 5x5 variation,
the advantage afforded by keeping the immediately surrounding layer around the
agent offsets this to such a degree that it creates an advantage.

A comparison of the best performing architectures can be seen in Figure 4. The
best and the worst performing architectures are global and local with padded
centering and global without centering respectively. The other 3 architectures
are clustered more closely together, with the 5 by 5 summary following behind
the padded centering variation of the global architecture and the global and
local integrated architecture with padded centering.

Figure 5: Mean standard deviation comparison after convergence

The end of training stability measured as the mean of standard deviation after
the convergence of most architectures, which is around the $500^{th}$ episode
mark, is shown in Figure 5. It can be seen that all the architectures with
centering are more stable compared to their no centering counterparts. This
difference is most pronounced in the global architecture. The results do not
show a clear stability advantage for either of the centering methods. The
summary architectures performed similarly, with the 5x5 variation showing a
tiny advantage over the smaller counterpart.

##  4 Discussion

The results show that using agency information to center the state space
around the agent increases performance regardless of the architecture.

The global and local architecture’s centering variations show the highest
learning performance among all the architectures. This is especially
pronounced in early learning, as the local network converges much faster as a
result of much smaller local state space. The conditional action selection
rule forces the agent to act close to optimality from very early on. This can
be seen both as an advantage and as a disadvantage, as the agent becomes
reactive very quickly. This means that whenever there is a reward in a single-
step distance, the agent learns to prioritize picking it up, but this can
result in sub-optimal behavior in a wide variety of cases. For example, the
agent would prefer to pick up a single reward one step away instead of the 4
rewards that are 2 steps away. This blindness to outside it’s immediate
surroundings causes it to perform well over what a global agent does at the
beginning but towards the end of the training it causes instability as it
continues to act sub-optimally from time to time. The global agent, on the
other hand, takes longer to learn but considers the whole state before acting
thus acts consistently optimal after a certain point. The global and local
integrated architecture performs well above the global architecture even when
there is no centering.

The simultaneous usage of global and local versions of the state in the
proposed architectures reminds of nested reactive and contextual controllers
as in the Distributed Adaptive Control [4] (see for example different ways of
combining reactive and adaptive control via reinforcement learning [3, 7]).
The difference here is that even the reactive is learned through interaction
with the environment. The local state can be used for reactive actions and the
global state for long term planning.

##  5 Conclusion

We have proposed different transformations of the input state of a
Reinforcement Learning (RL) agent that combine attention and agency detection
features; both have been addressed separately in RL but not jointly to our
knowledge. We have proposed and benchmarked different architectures including
both global and local agency centered versions of the state and also including
”summaries” of the surroundings. Results suggest that even a redundant global
local state network can learn faster than the global alone. ”Summarized”
versions of the state look promising to achieve input-size independence
learning.

Future studies will explore how the state transformations proposed in this
paper scale to larger state spaces with higher dimensions, and whether the
promise of ”summary transformations” to achieve input-size independence holds.
We will also investigate alternative architectures that can utilize
progressively larger state spaces as the training progresses.

## Acknowledgments

Research supported by INSOCO-DPI2016-80116-P.

## References

  * [1] Justin Brody, Samuel Levin, and Samuel Shapiro.  Learning knowledge of agency.  In 2017 IEEE International Conference on Autonomic Computing (ICAC), pages 263–270. IEEE, 2017.
  * [2] Christopher P Burgess, Loic Matthey, Nicholas Watters, Rishabh Kabra, Irina Higgins, Matt Botvinick, and Alexander Lerchner.  Monet: Unsupervised scene decomposition and representation.  arXiv preprint arXiv:1901.11390, 2019.
  * [3] Ismael T Freire, Clement Moulin-Frier, Marti Sanchez-Fibla, Xerxes D Arsiwalla, and Paul Verschure.  Modeling the formation of social conventions in multi-agent populations.  arXiv preprint arXiv:1802.06108, 2018.
  * [4] Giovanni Maffei, Diogo Santos-Pata, Encarni Marcos, Marti Sánchez-Fibla, and Paul FMJ Verschure.  An embodied biologically constrained model of foraging: from classical and operant conditioning to adaptive real-world behavior in dac-x.  Neural Networks, 72:88–108, 2015.
  * [5] Volodymyr Mnih, Nicolas Heess, Alex Graves, et al.  Recurrent models of visual attention.  In Advances in neural information processing systems, pages 2204–2212, 2014.
  * [6] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  Nature, 518(7540):529, 2015.
  * [7] Clément Moulin-Frier, Marti Sanchez-Fibla, and Paul FMJ Verschure.  Autonomous development of turn-taking behaviors in agent populations: a computational study.  In 2015 Joint IEEE International Conference on Development and Learning and Epigenetic Robotics (ICDL-EpiRob), pages 188–195. IEEE, 2015.
  * [8] Yael Niv, Reka Daniel, Andra Geana, Samuel J Gershman, Yuan Chang Leong, Angela Radulescu, and Robert C Wilson.  Reinforcement learning in multidimensional environments relies on attention mechanisms.  Journal of Neuroscience, 35(21):8145–8157, 2015.
  * [9] Martí Sánchez-Fibla, Sébastien Forestier, Clément Moulin-Frier, Jordi-Ysard Puigbò, and Paul FMJ Verschure.  From motor to visually guided bimanual affordance learning.  Adaptive Behavior, pages 1–16, 2019.
  * [10] Martí Sánchez-Fibla, Clément Moulin-Frier, Xerxes D Arsiwalla, and Paul FMJ Verschure.  Social sensorimotor contingencies: Towards theory of mind in synthetic agents.  In CCIA, pages 251–256, 2017.
  * [11] Valentin Thomas, Jules Pondard, Emmanuel Bengio, Marc Sarfati, Philippe Beaudoin, Marie-Jean Meurs, Joelle Pineau, Doina Precup, and Yoshua Bengio.  Independently controllable features.  arXiv preprint arXiv:1708.01289, 2017.
  * [12] Harm van Seijen, Mehdi Fatemi, Joshua Romoff, Romain Laroche, Tavian Barnes, and Jeffrey Tsang.  Hybrid reward architecture for reinforcement learning.  In In Advances in Neural Information Processing, pages 5392–5402, 2017.


# Development of novel low-mass module concepts based on MALTA monolithic
pixel sensors

J Weick1,2, F Dachs1, P Riedler1, M Vicente Barreto Pinto4, A M. Zoubir2, L
Flores Sanz de Acedo1, I Asensi Tortajada1, V Dao1, D Dobrijevic1,5, H
Pernegger1, M Van Rijnbach1,3, A Sharma1, C Solans Sanchez1, R de Oliveira1, D
Dannheim1, J V Schmidt1,6

###### Abstract

The MALTA CMOS monolithic silicon pixel sensors has been developed in the
Tower 180 nm CMOS imaging process. It includes an asynchronous readout scheme
and complies with the ATLAS inner tracker requirements for the HL-LHC. Several
4-chip MALTA modules have been built using Al wedge wire bonding to
demonstrate the direct transfer of data from chip-to-chip and to read out the
data of the entire module via one chip only. Novel technologies such as
Anisotropic Conductive Films (ACF) and nanowires have been investigated to
build a compact module. A lightweight flex with 17 µm trace spacing has been
designed, allowing compact packaging with a direct attachment of the chip
connection pads to the flex using these interconnection technologies. This
contribution shows the current state of our work towards a flexible, low
material, dense and reliable packaging and modularization of pixel detectors.

##  1 Introduction

The upcoming upgrades of the LHC experiments and future detectors are setting
new requirements for particle trackers including increased radiation hardness,
timing and spacial resolution and rate capability as well as dense integration
with a minimal material budget. To realize very large detector surfaces, a
scalable production process to manufacture chip modules is also mandatory.
This work will show a part of the current efforts of CERNs experimental
physics R&D (EP-R&D) [1] project to develop flexible, low material, dense,
reliable and scalable modules using radiation tolerant pixel chips.

##  2 Modularization of MALTA

Figure 1: Four chip MALTA module demonstrating the data transfer from
secondary (S1-S3) to the primary chip

The MALTA chip is a monolithic pixel sensor produced in the 180nm Tower
process featuring an asynchronous front-end and read-out. It has proven NIEL
radiation hardness up to $3\cdot 10^{15}$ neq/cm2 , and TID hardness up to 100
Mrad.[2]
The data transfer from the secondary (S1-S3) to the primary chip (Prim) has
been demonstrated in a 4-chip MALTA module shown in figure 1 placed on a rigid
PCB carrier housing over one million pixels. The interconnection from chip-to-
chip and from chip to PCB is realized using wire-bonds. Current studies focus
on the replacement of wire bonds for chip-to-chip data and power transmission
with a silicon interposer (silicon bridge). This allows for a denser
integration of the chips, compared to wire bonding, as no minimum spacing
between the chips is needed. Furthermore, a flexible carrier (flex) has been
designed to interconnect four MALTA2 chips using a flip-chip [3] process,
connecting the chip pads to the respective pads on the flex directly.

##  3 Interconnection technologies

Figure 2: ACF (black dots) on ENIG plated MALTA pad

The small pad size of MALTA and its dense pad layout require the study of new
interconnection technologies such as anisotropic conductive films (ACF) or a
surface nano structuration process (nanowires). These technologies have the
potential to provide a scalable chip-to-chip or chip-to-flex interconnection
realizable in a fast interconnection process and are suitable for a large
number of pads. The interconnection is demonstrated using the aluminum pads of
size 88$\times$88 µm2 of the MALTA chip.

###  3.1 Anisotropic conductive film (ACF)

ACF is a industry standard interconnection technology used in LCD screen
production [4]. The interconnection is established with metal-coated polymer
particles, embedded in glue. Figure 2 shows the ACF balls (black dots) on the
MALTA pads. In a preparatory step, the Aluminium pads are plated using
Electroless Nickel Immersion Gold (ENIG) [5], which serves as an elevation
layer for the ACF particles and prevents the formation of an oxide layer.
Afterwards, the device to be bonded is laminated with the ACF. Finally, the
assembly is done in a flip-chip process using pressure to compress the ACF
conductive particles between pads and heat to cure the glue. As such, ACF
provides a cost-effective, maskless, and in-house capable assembly technology.
ACF is currently developed as a bonding process for the silicon interposer for
MALTA modules, and will be used in the flip chip assembly of the MALTA2 chips
on the flex carrier introduced in section 5.

###  3.2 Nanowires

Nanowires are evaluated as a second interconnection technology. For this
bonding process, a titanium layer is deposited on the aluminum pads of MALTA
together with a gold finish to prevent oxidation. This serves as a base for a
copper seed layer on which nanowires with a diameter in the hundred-nanometer
range, and a length of several micrometers are grown. Figure 3 shows the
copper nanowires on a MALTA pad.
The bonding process can be realized using three different procedures, which
differs in their applied pressure and heat, and the necessity to apply the
nanowires on only one side (chip pads or targeted carrier pads), or on both:

Figure 3: Copper nanowires grown on 88$\times$88 µm2 MALTA pad

  * •

Sinter process: The wires are applied to one side only. The connection is
formed via a sintering process that requires high pressure and heat, compared
to the other procedures.

  * •

Cold welding process: Wires are applied on both sides and allow for a large
contact surface. The connection is established with a cold-welding process
that requires minimal pressure and heat.

  * •

Gluing process: In this bonding process nanowires are only applied on one
side. A non-conductive glue is used as underfill which allows for reduced
pressure and heat and enhanced mechanical stability.

Nanowires promise to offer low contact resistance and parasitic
inductance/capacitance, and can be applied either on the targeted carrier or
directly on the chip (chip or wafer level).

##  4 Interconnection test structure

A test structure has been developed on a 300 µm aluminum nitride (AlN) ceramic
to validate the introduced interconnection technologies electrically and
mechanically as well as pre-optimizing the process parameters for
interconnecting the MALTA2 chips with the flex presented in section 5.

Figure 4: Concept of the silicon bridge test setup, to test the electrical
characteristic of two ACF interconnections

Figure 5: ACF bonded silicon MALTA interposer and reference on test structure
for electrical characterization.

Figure 6: Signal dampening from 0 to 3 GHz over a ACF bonded silicon bridge
and reference structure

AlN has been chosen due to its similar thermal conductivity to silicon and
compatibility with the manufacturing process of the flex. The various pad
layouts of this structure mirror the pads of the MALTA chip and the silicon
interposer. They are designed to study, among other parameters, the bond
success rate per pad, the probability of electrical shorts between neighboring
pads and the resistivity of the interconnection. First electrical tests
indicate a DC resistance between 1.7 to 3 for the ACF interconnection on the
88$\times$88 µm2 MALTA pad using an ACF with 3 µm Ni-Au/Polymer conductive
particles, while the current AlSi wire bonds with a diameter of 25µm feature a
resistance of <1 on our current carriers [6]. The setup to test the insertion
loss of a differential signal over an ACF connection compared to a directly
wired reference is shown in figure 4. The silicon bridge is bonded onto the
test structure using ACF, and establishes a electrical connection between the
probing pads. Figure 6 shows the bonded bridge on the substrate with the
silicon bridge in top and the reference structure on the bottom.
Since the structure is optimized for mechanical test rather than for high
frequencies (HF) it only allows for a qualitative statement of the signal
decay compared to the reference. The signal decay has been evaluated using a
vector network analyzer with Picotest probes which allow to probe the large
probing pads directly. First results are shown in figure 6.
The signal magnitude over the reference as well as over the ACF
interconnection decays at higher frequencies. The measured offset of the ACF
connection in relation to the reference (<2dB) is indicating an acceptable
signal loss for our purposes.The difference between ACF channel 1 and ACF
channel 2 is in line with the spread in DC resistance between different pads
and a result of the non optimized bonding process. To validate the signal
transfer over ACF, further investigation in combination with a dedicated HF
test structure is needed.

##  5 Low mass flexible MALTA2 carrier

A Low mass flexible MALTA2 carrier (flex) for a 4-chip module is currently
produced as a proof-of-concept for flip-chip mounting the MALTA2 chip on a
flexible support structure, using minimal material while providing maximal
testing capabilities. Figure 7 shows a model of the first flex prototype. We
use the data readout scheme validated with the four-chip MALTA PCB in section
2, transferring the data from three secondary chips (S1-S3) to a primary chip
(Prim) and from there over a dedicated connector flex circuit to the data
acquisition FPGA. The layout of the flex allows for the chips to be tuned and
powered individually. This gives us the possibility to test the influence of
constrained powering on the performance and the data transfer capabilities of
the module.

Figure 7: Flex carrier for four MALTA2 chips with chip to chip data transfer

Due to the pad layout of MALTA, wire bonds only allow for arranging the chips
in a single row module. This constraint does not apply to modules assembled on
a flex circuit using a flip chip process. Furthermore, chips can be supplied
with power through the flex support structure allowing to increase the module
size compared to chip-to-chip powering. The same holds true if the tiling is
replaced by a wafer-scale integrated sensor using stitched devices.

Figure 8: Layout (left) and produced flex (right)

The dense pad layout of the MALTA chip requires a flex circuit with fine
structures in order to keep capacitive loads low and minimize the number of
metal layers and thus material budget.
The chosen flex production technology allows for structure sizes down to 15 µm
track and clearance, a 10 µm polyamide layer thickness, and a 6 µm copper
thickness. Together with 20 µm solder stop, the designed flex circuit has an
overall thickness of roughly 50 µm. The 20 µm solder stop is only needed for
assembly and population of the circuit as well as to enable soldering on debug
pads. Figure 8 shows the manufactured flex on the right side and the
respective layout on the left.

##  6 Summary and outlook

In this work, we present first results from studies on mechanically robust and
scalable interconnection techniques, which could offer an alternative to wire-
bonding.
We show an approach to densely package multiple MALTA pixel chips onto a
flexible module carrier minimizing the needed material. In a next step, the
flex will be assembled using the introduced interconnection technologies,
followed by tests in the lab and at test beam to quantify the performance of
the module.

## References

  * [1] https://ep-rnd.web.cern.ch/
  * [2] Mini-MALTA: radiation hard pixel designs for small-electrode monolithic CMOS sensors for the High Luminosity LHC, M. Dyndal et al 2020 JINST 15 P02005.
  * [3] Tsukada, Yutaka. (2010). Flip chip technology. Proceedings of the IEEE/CPMT International Electronics Manufacturing Technology (IEMT) Symposium. 10.1109/IEMT.2010.5746775.
  * [4] Yim, Myung Jin & Paik, Kyung-Wook. (1998). Design and understanding of Anisotropic Conductive Films (ACF’s) for LCD packaging. Components, Packaging, and Manufacturing Technology, Part A, IEEE Transactions on. 21. 226 - 234. 10.1109/95.705468.
  * [5] Janis Viktor Schmidt, _Pixel detector hybridisation and integration with Anisotropic Conductive Films_ , Subm. to proceedigs of the Topical workshop on electronics for particle physics (2022).
  * [6] Bonding Wires for Semiconductor Technology, Heraeus Deutschland GmbH & Co. KG, www.heraeus-electronics.com