Dem Institut für Mathematik der Technischen Universität Berlin vorgelegte
Masterarbeit
von
Matrikelnummer 399787.
Betreuer und Erstgutachter: Prof. Dr. Christoph Knochenhauer
Zweitgutachter: PD Dr. Pierre Schnizer
Eidesstattliche Erklärung
Hiermit erkläre ich, dass ich die vorliegende Arbeit selbstständig und eigenhändig sowie ohne unerlaubte fremde Hilfe und ausschließlich unter Verwendung der aufgeführten Quellen und Hilfsmittel angefertigt habe.
Berlin, den 31.01.2024
Alexander Schütt
Zusammenfassung
In dieser Arbeit wird das Prinzip des Reinforcement Learnings auf ein reales Problem angewandt. Ziel der Arbeit ist die Injektionseffizienz von BESSY II zu optimieren.
Zuerst werden die Grundlagen des Reinforcement Learnings zusammengetragen. Wir beweisen unter welchen Annahmen sich mit dem Optimalitätsprinzip von Bellman optimale Strategien finden lassen und stellen zwei auf dem genannten Prinzip basierenden Algorithmen vor. Zusätzlich wird gezeigt, wie die Parameter der Algorithmen automatisch auf das Problem optimiert werden können.
Danach widmen wir uns der Anwendung. Zunächst wird die Synchrotronstrahlungsquelle BESSY II vorgestellt. Wir werden auf die einzelnen Bauteile genauer eingehen, insbesondere auf den Non-Linear Kicker. Jener wird bei der zu optimierenden Injektion verwendet. Um ein Verständnis der Injektion von Elektronen mit dem Non-Linear Kicker aufzubauen, wird gezeigt unter welcher notwendigen Bedingung eine Injektion erfolgreich sein kann.
Daraufhin stellen wir drei verschiedene Modelle vor, wie man die Injektion mathematisch beschreiben kann. Die Modelle unterscheiden sich darin, wie viele Elektronen injiziert werden und wann entschieden werden kann in welcher Runde der Non-Linear Kicker aktiviert wird.
Um gute Modelle mit den vorgestellten Reinforcement Learning Algorithmen zu erhalten, zeigen wir, wie wir eine Simulation der BESSY II Injektion approximiert haben, um diese signifikant zu beschleunigen.
Zum Schluss zeigen wir die besten Injektionsstrategien in allen 3 Modellen und wie man diese für die reale Synchrotronstrahlungsquelle BESSY II benutzen kann.
Introduction
In this thesis, we show how stochastic control algorithms are used to increase the injection efficiency of BESSY II. We also give an outlook on how to fully automate the injection process at BESSY II. We start with an introduction to the electron injection at BESSY II and reinforcement learning.
Electron Injection at BESSY II
This thesis explores the application of stochastic control algorithms, specifically reinforcement learning algorithms, to a real world application. The goal is to improve the electron injection efficiency of BESSY II.
BESSY II is a synchrotron light source located in Adlershof, Berlin. First, it accelerates electrons in a synchrotron and then stores them in a storage ring. Then, the stored electrons are accelerated in various directions to generate synchrotron light. To maintain the energy of the synchrotron light at a constant level, new electrons need to be injected regularly. Typically, these injections happen roughly every three minutes. Currently, electrons are injected by a 4-kicker bump:
In a first step, the stored electrons, that create the synchrotron light, are kicked out of their initial path by 2 magnets (called K1,K2 in Figure 1.1 ). The redirected electrons
Figure 1.1. 4-Kicker bump, by [1].
Introduction
are then merged with newly injected electrons before being kicked back (by magnets K 3 , K 4 K_3,K_4 K 3 , K 4 ) to the stored beam position.
This process causes disturbances in the path of the stored electrons, which reduces the quality of the synchrotron light and additionally risks losing a significant fraction of the electrons in the storage ring during this injection procedure.
A new injection procedure, called the Non-Linear Kicker Injection, has been introduced to BESSY II, see [2]. This method uses a single magnet with a non-linear magnetic field to inject the electrons, as shown in the figure below.
This injection method has the advantage of only minimally affecting the stored electrons whose x x x values are very close to 0, as the magnetic field strength is almost 0 in this region (see Figure 1.2 ). As a result, the stored electrons are only slightly disturbed and the quality of the synchrotron light is not deteriorated.
Figure 1.2. The magnetic field of the non-linear kicker. On the x axis the x-dimensional distance to the centre of the beam line is shown. On the y axis the corresponding amount of magnetic field strength is shown.
This non-linear kicker magnet has already been installed at BESSY II in 2011, see [2]. It is currently not used because the injection efficiency is lower compared to the 4-kicker bump. Recently some progress has been made to increase the efficiency by optimising the strength of the magnets leading to the non-linear kicker.
Reinforcement Learning
Reinforcement learning is a subfield of machine learning that deals with decision-making. Its foundation is based on learning by interaction, which is inspired by the way humans learn.
Through interactions, we humans can analyse how the environment around us responds to our actions. Given such a response, we get the information on whether the environment has changed in the desired way, or if we need to adapt our actions.
Consider, for example, a game of chess. The outcome of a game is influenced by the actions taken, whether it results in a win, loss or draw. Based on the outcome, we may adjust our play style to improve our chances of winning future games.
In reinforcement learning, this concept is applied. Reinforcement learning algorithms explore the environment to find a policy that maximise a numerical reward.
The mathematical foundation of reinforcement learning are Markov Decision Models. They describe the environment by providing the state and action spaces, the dynamics between them, such that the Markov property holds and additionally a reward system that rewards/punishes the agent for taking good/bad actions. Social science speaks about positive/negative reinforcement.
Once we have defined Markov Decision Models, we use the Markov property of the environment to show fundamental mathematical connections that allow us to compute optimal policies.
As these optimal policies can only be computed efficiently in discrete and finite cases, we describe different reinforcement learning algorithms. They use the mathematical connections, but in an approximate way, using neural networks. Allowing efficient calculations for continuous action and state spaces. Finally, we apply them to the injection problem.
Scope of the Thesis
This thesis is structured as follow:
Chapter 2 introduces the mathematical foundation of Reinforcement Learning. We define Markov Decision Processes and prove under which conditions the Bellman equation holds. After that, we present different algorithms for the search of good strategies.
In chapter 3, the physics models are introduced, which are the basis of the used simulation. These shall give a concise description of the physics involved.
Chapter 4 describes how the Markov decision models are formulated. In total we give 4 formulations: The first formulation describes the actual problem in BESSY II. After that we see three formulations that are able to be solved by reinforcement learning algorithms. We show the 1000-step single-electron injection, the 1000-step 1000-electron injection and finally the 1-step 1000-electron injection.
As the preceding chapters laid out the foundations, chapter 5 presents how the reinforcement learning algorithms are applied to the injection problem and gives its training results.
Reinforcement Learning
This chapter is based on chapter 2 of the book Markov decision processes with applications to finance [3] by Nicole Bäuerle and Ulrich Rieder. Some adaptations have been made, to fit the setting of our application better. For example, the set of admissible actions is identical in each state, as this is the case in our application and it simplifies the model.
We start this chapter by presenting the foundations of reinforcement learning. After the definition of a Markov Decision Model/Process, policies and the value function, we show the Bellman equation and prove that under some conditions we can find optimal policies using the Bellman equation. Next, we present temporal difference learning and two algorithms to find good policies. After that, we introduce partially observable Markov decision processes, that are needed in the non-linear kicker injection problem. At the end, we describe the process of the hyperparameter search and present different algorithms for the hyperparameter search.
Markov Decision Processes
Definition 2.1.1 (Markov Decision Model). A Markov Decision Model with planning horizon N ∈ N N \in\mathbb{N} N ∈ N is a tuple ( E , A , p , p 0 , r , β , g ) (E,A,p,p_0,r,\beta,g) ( E , A , p , p 0 , r , β , g ) , where:
E E E is a measurable space with σ \sigma σ -algebra E \mathcal{E} E , called state space
A A A is a measurable space with σ \sigma σ -algebra A \mathcal{A} A , called action space
p p p is a stochastic transition kernel from E × A E \times A E × A to E E E , i.e. for all ( x , a ) ∈ E × A (x,a) \in E \times A ( x , a ) ∈ E × A and B ∈ E B \in\mathcal{E} B ∈ E , the function B ↦ p ( B ∣ x , a ) B \mapsto p(B|x,a) B ↦ p ( B ∣ x , a ) is a probability measure on E \mathcal{E} E and the mapping ( x , a ) ↦ p ( B ∣ x , a ) (x,a) \mapsto p(B|x,a) ( x , a ) ↦ p ( B ∣ x , a ) is measurable. The value p ( B ∣ x , a ) p(B|x,a) p ( B ∣ x , a ) is the probability that if at any time n n n in state x ∈ E x \in E x ∈ E the action a a a is taken, the next state at time n + 1 n+1 n + 1 is in B B B .
p 0 p_0 p 0 is called initial probability on E E E
r : E × A → R r : E \times A \to\mathbb{R} r : E × A → R is a measurable function, called reward function
discount factor β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ]
g : E → R g : E \to\mathbb{R} g : E → R is a measurable function, called terminal reward function
Our goal now is to define a random process on the Markov Decision Model ( E , A , p , p 0 , r , β , g ) (E, A, p, p_0, r, \beta, g) ( E , A , p , p 0 , r , β , g ) with planning horizon N ∈ N N \in\mathbb{N} N ∈ N . The random process is going to take values in the state space, that can be influenced by the actions taken. For this, we consider the following measurable space:
Ω : = E N + 1 with σ -algebra F : = ⨂ n = 0 N E , \Omega:= E^{N+1} \quad\text{with } \sigma\text{-algebra } \mathcal{F} := \bigotimes_{n=0}^{N} \mathcal{E}, Ω := E N + 1 with σ -algebra F := n = 0 ⨂ N E ,
where ( E , E ) (E,\mathcal{E}) ( E , E ) is the state space.
Definition 2.1.2 (Markov Decision Process). Let M = ( E , A , p , p 0 , r , β , g ) M = (E, A, p, p_0, r, \beta, g) M = ( E , A , p , p 0 , r , β , g ) , N ∈ N N \in\mathbb{N} N ∈ N and ( Ω , F ) (\Omega, \mathcal{F}) ( Ω , F ) be as above. For all n ∈ { 0 , … , N } n \in\{0,\ldots,N\} n ∈ { 0 , … , N } and ω = ( ω 0 , … , ω N ) ∈ Ω \omega= (\omega_0,\ldots,\omega_N) \in\Omega ω = ( ω 0 , … , ω N ) ∈ Ω , we define
X n ( ω ) = X n ( ( ω 0 , … , ω N ) ) : = ω n . X_n(\omega) = X_n((\omega_0,\ldots,\omega_N)) := \omega_n. X n ( ω ) = X n (( ω 0 , … , ω N )) := ω n . The random process X = { X n } n = 0 , … , N X = \{X_n\}_{n=0,\ldots,N} X = { X n } n = 0 , … , N is called Markov Decision Process.
Since F \mathcal{F} F is the product σ \sigma σ -algebra on Ω \Omega Ω , the functions X n X_n X n are measurable, as they are projections.
In the following, we assume that ( E , A , p , p 0 , r , β , g ) (E, A, p, p_0, r, \beta, g) ( E , A , p , p 0 , r , β , g ) denotes a Markov Decision Model with planning horizon N ∈ N N \in\mathbb{N} N ∈ N and X = { X n } n = 0 , … , N X = \{X_n\}_{n=0,\ldots,N} X = { X n } n = 0 , … , N denotes a Markov Decision Process on ( Ω , F ) (\Omega,\mathcal{F}) ( Ω , F ) .
To allow the Markov Decision Process to depend on the actions taken, we first define the set of valid actions:
Definition 2.1.3 (decision rule/ policy). We call a measurable map f : E → A f:E \to A f : E → A a decision rule. A sequence of decision rules π = ( f 0 , … , f N − 1 ) \pi= (f_0,\ldots,f_{N-1}) π = ( f 0 , … , f N − 1 ) is called policy. The set of all policies is denoted by Ξ \Xi Ξ .
Note that if we assume that the state space E E E and action space A A A are not empty, the set of all policies Ξ \Xi Ξ is not empty, as all constant mappings f : E → A f:E \to A f : E → A are measurable.
Remark 2.1.4. Now, we can describe a Markov Decision Process which depends on a policy.
Let π = ( f 0 , … , f N − 1 ) \pi= (f_0,\ldots,f_{N-1}) π = ( f 0 , … , f N − 1 ) be a fixed policy and x ∈ E x \in E x ∈ E an initial state. One can show that there exists a unique probability measure P x π \mathbb{P}^{\pi}_x P x π on ( Ω , F ) (\Omega,\mathcal{F}) ( Ω , F ) , such that for all B ∈ E B \in\mathcal{E} B ∈ E :
P x π ( X 0 ∈ B ) = δ x ( B ) \mathbb{P}^{\pi}_x(X_0 \in B) = \delta_x(B) P x π ( X 0 ∈ B ) = δ x ( B ) ,
P x π ( X n + 1 ∈ B ∣ X 1 , … , X n ) = P x π ( X n + 1 ∈ B ∣ X n ) = p ( B ∣ X n , f n ( X n ) ) \mathbb{P}^{\pi}_x(X_{n+1} \in B \mid X_1,\ldots,X_n) = \mathbb{P}^{\pi}_x(X_{n+1} \in B \mid X_n) = p(B \mid X_n, f_n(X_n)) P x π ( X n + 1 ∈ B ∣ X 1 , … , X n ) = P x π ( X n + 1 ∈ B ∣ X n ) = p ( B ∣ X n , f n ( X n )) .
Reinforcement Learning
The second property is called Markov property, which tells us, that the next state only depends on the current state and action chosen, and it does not depend on the history of states and chosen actions.
Note that in our analysis, we will not go into detail about the initial probability p 0 p_0 p 0 , as the next definitions all depend on a current state x ∈ E x \in E x ∈ E at some time point n n n .
Further, note that in our definition of P x π \mathbb{P}^{\pi}_{x} P x π , the actions are applied indirectly by having the measure P x π \mathbb{P}^{\pi}_{x} P x π depend on the policy π \pi π .
From now on, we denote by P x π \mathbb{P}^{\pi}_{x} P x π the probability measure from above, given policy π ∈ Ξ \pi\in\Xi π ∈ Ξ and initial state x ∈ E x \in E x ∈ E , and by E x π \mathbb{E}^{\pi}_{x} E x π the expectation w.r.t. P x π \mathbb{P}^{\pi}_{x} P x π . Further, we define P n x π \mathbb{P}^{\pi}_{n x} P n x π as conditional probability P n x π ( ⋅ ) : = P π ( ⋅ ∣ X n = x ) \mathbb{P}^{\pi}_{n x}(\cdot) := \mathbb{P}^{\pi}(\cdot\mid X_n = x) P n x π ( ⋅ ) := P π ( ⋅ ∣ X n = x ) , which is well-defined by the Markov property. Denote by E n , x π \mathbb{E}^{\pi}_{n,x} E n , x π the associated expectation.
We move on to compare the performances of different policies within a Markov Decision Model. In order to ensure that the following definitions are well defined, we impose following assumption:
Let r + : E × A → R ≥ 0 r^{+}: E \times A \to\mathbb{R}_{\ge0} r + : E × A → R ≥ 0 and g + : E → R ≥ 0 g^{+}: E \to\mathbb{R}_{\ge0} g + : E → R ≥ 0 denote the positive part of r r r and g g g , i.e. for all x ∈ E x \in E x ∈ E and a ∈ A a \in A a ∈ A
r + ( x , a ) = max { r ( x , a ) , 0 } and g + ( x ) = max { g ( x ) , 0 } . r^{+}(x,a) = \max\{r(x,a),0\}\quad\text{and}\quad g^{+}(x) = \max\{g(x),0\}. r + ( x , a ) = max { r ( x , a ) , 0 } and g + ( x ) = max { g ( x ) , 0 } .
Henceforth, we assume that the following inequality holds for all n ∈ { 0 , … , N } n \in\{0,\ldots,N\} n ∈ { 0 , … , N } and x ∈ E x \in E x ∈ E :
sup π E n , x π [ ∑ k = n N − 1 β k r + ( X k , f k ( X k ) ) + β N g + ( X N ) ] < ∞ , (1) \sup_{\pi}\mathbb{E}^{\pi}_{n,x}\left[\sum_{k=n}^{N-1}\beta^{k}r^{+}(X_k,f_k(X_k))+\beta^{N}g^{+}(X_N)\right] < \infty, \tag*{(1)} π sup E n , x π [ k = n ∑ N − 1 β k r + ( X k , f k ( X k )) + β N g + ( X N ) ] < ∞ , (1)
where the supremum is taken over all policies π = ( f 0 , … , f N − 1 ) ∈ Ξ \pi=(f_0,\ldots,f_{N-1}) \in\Xi π = ( f 0 , … , f N − 1 ) ∈ Ξ .
Definition 2.1.5 (policy reward). Let π = ( f 0 , … , f N − 1 ) ∈ Ξ \pi=(f_0,\ldots,f_{N-1}) \in\Xi π = ( f 0 , … , f N − 1 ) ∈ Ξ be a policy. The expected total reward starting at time n n n , given policy π \pi π and state x ∈ E x \in E x ∈ E is defined as
V n , π ( x ) : = E n , x π [ ∑ k = n N − 1 β k r ( X k , f k ( X k ) ) + β N g ( X N ) ] ∈ [ − ∞ , ∞ ) . V_{n,\pi}(x) := \mathbb{E}^{\pi}_{n,x}\left[\sum_{k=n}^{N-1}\beta^{k}r(X_k,f_k(X_k))+\beta^{N}g(X_N)\right] \in[-\infty,\infty). V n , π ( x ) := E n , x π [ k = n ∑ N − 1 β k r ( X k , f k ( X k )) + β N g ( X N ) ] ∈ [ − ∞ , ∞ ) .
The maximal expected reward starting at time n n n is given as
V n ( x ) : = sup π V n , π ( x ) ∈ [ − ∞ , ∞ ) , V_n(x) := \sup_{\pi} V_{n,\pi}(x) \in[-\infty,\infty), V n ( x ) := π sup V n , π ( x ) ∈ [ − ∞ , ∞ ) ,
for x ∈ E x \in E x ∈ E . We call the function V n : E → R V_n:E \to\mathbb{R} V n : E → R value function.
Remark 2.1.6. By Assumption A N A_N A N the mappings V n , π V_{n,\pi} V n , π and V n V_n V n are both well defined. If there exists a policy π ∈ Ξ \pi\in\Xi π ∈ Ξ with V 0 , π ( x ) = V 0 ( x ) V_{0,\pi}(x) = V_0(x) V 0 , π ( x ) = V 0 ( x ) for all x ∈ E x \in E x ∈ E , we call the policy π \pi π optimal and denote the optimal policy π \pi π by π ∗ \pi^* π ∗ .
Bellman Equation
In the last section we defined Markov Decision Processes on Markov Decision Models, together with policies. In this section we show how to iteratively calculate the value function V n , π V_{n,\pi} V n , π of a policy π \pi π .
Theorem 2.2.1 (reward iteration). Let π = ( f 0 , … , f N − 1 ) ∈ Ξ \pi=(f_0,\ldots,f_{N-1})\in\Xi π = ( f 0 , … , f N − 1 ) ∈ Ξ be a policy. Then, for all n = 0 , 1 , … , N − 1 n=0,1,\ldots,N-1 n = 0 , 1 , … , N − 1 :
V n , π ( x ) = β n r ( x , f n ( x ) ) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x ) ) V_{n,\pi}(x)=\beta^n r(x,f_n(x))+\int_E V_{n+1,\pi}(x')p(\mathrm{d}x'|x,f_n(x)) V n , π ( x ) = β n r ( x , f n ( x )) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x )) , for all x ∈ E x\in E x ∈ E ,
V N , π ( x ) = β N g ( x ) V_{N,\pi}(x)=\beta^N g(x) V N , π ( x ) = β N g ( x ) , for all x ∈ E x\in E x ∈ E .
Proof. eq:2 follows due to
V N , π ( x ) = E N , x π [ ∑ k = N N − 1 β k r ( X k , f k ( X k ) ) + β N g ( X N ) ] = E N , x π [ β N g ( X N ) ] = E π [ β N g ( X N ) ∣ X N = x ] = β N g ( x ) , \begin{aligned}
V_{N,\pi}(x)=\mathbb{E}^{\pi}_{N,x}\left[\sum_{k=N}^{N-1}\beta^k r(X_k,f_k(X_k))+\beta^N g(X_N)\right] \\
&=\mathbb{E}^{\pi}_{N,x}\left[\beta^N g(X_N)\right]=\mathbb{E}^{\pi}\left[\beta^N g(X_N)\mid X_N=x\right]=\beta^N g(x),
\end{aligned} V N , π ( x ) = E N , x π [ k = N ∑ N − 1 β k r ( X k , f k ( X k )) + β N g ( X N ) ] = E N , x π [ β N g ( X N ) ] = E π [ β N g ( X N ) ∣ X N = x ] = β N g ( x ) ,
for all x ∈ E x\in E x ∈ E .
Now, we show equation 1. Let x ∈ E x\in E x ∈ E be arbitrary. By definition, we get
V n , π ( x ) = E n , x π [ ∑ k = n N − 1 β k r ( X k , f k ( X k ) ) + β N g ( X N ) ] = E n , x π [ β n r ( x , f n ( x ) ) ] + E n , x π [ ∑ k = n + 1 N − 1 β k r ( X k , f k ( X k ) ) + β N g ( X N ) ] . \begin{aligned}
V_{n,\pi}(x)=\mathbb{E}^{\pi}_{n,x}\left[\sum_{k=n}^{N-1}\beta^k r(X_k,f_k(X_k))+\beta^N g(X_N)\right] \\
&=\mathbb{E}^{\pi}_{n,x}\left[\beta^n r(x,f_n(x))\right]+\mathbb{E}^{\pi}_{n,x}\left[\sum_{k=n+1}^{N-1}\beta^k r(X_k,f_k(X_k))+\beta^N g(X_N)\right].
\end{aligned} V n , π ( x ) = E n , x π [ k = n ∑ N − 1 β k r ( X k , f k ( X k )) + β N g ( X N ) ] = E n , x π [ β n r ( x , f n ( x )) ] + E n , x π [ k = n + 1 ∑ N − 1 β k r ( X k , f k ( X k )) + β N g ( X N ) ] .
Using the tower property of conditional expectations we get
V n , π ( x ) = β n r ( x , f n ( x ) ) + E n , x π [ E n , x π [ ∑ k = n + 1 N − 1 β k r ( X k , f k ( X k ) ) + β N g ( X N ) | X n + 1 ] ] = β n r ( x , f n ( x ) ) + ∫ E E n + 1 , x ′ π [ ∑ k = n + 1 N − 1 β k r ( X k , f k ( X k ) ) + β N g ( X N ) ] p ( d x ′ ∣ x , f n ( x ) ) = β n r ( x , f n ( x ) ) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x ) ) , \begin{aligned}
V_{n,\pi}(x)=\beta^n r(x,f_n(x))+\mathbb{E}^{\pi}_{n,x}\left[\mathbb{E}^{\pi}_{n,x}\left[\sum_{k=n+1}^{N-1}\beta^k r(X_k,f_k(X_k))+\beta^N g(X_N)\middle|X_{n+1}\right]\right] \\
&=\beta^n r(x,f_n(x))+\int_E\mathbb{E}^{\pi}_{n+1,x'}\left[\sum_{k=n+1}^{N-1}\beta^k r(X_k,f_k(X_k))+\beta^N g(X_N)\right]p(\mathrm{d}x'|x,f_n(x)) \\
&=\beta^n r(x,f_n(x))+\int_E V_{n+1,\pi}(x')p(\mathrm{d}x'|x,f_n(x)),
\end{aligned} V n , π ( x ) = β n r ( x , f n ( x )) + E n , x π [ E n , x π [ k = n + 1 ∑ N − 1 β k r ( X k , f k ( X k )) + β N g ( X N ) X n + 1 ] ] = β n r ( x , f n ( x )) + ∫ E E n + 1 , x ′ π [ k = n + 1 ∑ N − 1 β k r ( X k , f k ( X k )) + β N g ( X N ) ] p ( d x ′ ∣ x , f n ( x )) = β n r ( x , f n ( x )) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x )) ,
where the second equation follows remark 2.1.4 P x π ( X n + 1 ∈ B ∣ X n ) = p ( B ∣ X n , f n ( X n ) ) \mathbb{P}^{\pi}_x(X_{n+1}\in B|X_n)=p(B|X_n,f_n(X_n)) P x π ( X n + 1 ∈ B ∣ X n ) = p ( B ∣ X n , f n ( X n )) .
Bellman Equation
Given Theorem 2.2.1 , we are able to calculate iteratively the value function V n , π V_{n,\pi} V n , π of a policy π \pi π . For the remaining part of this section we concentrate on calculating an optimal policy.
This equation is called the Bellman equation.
By definition 2.1.5, the maximal expected reward at time N N N starting in x ∈ E x\in E x ∈ E has to be β N g ( x ) \beta^N g(x) β N g ( x ) . On the other hand, at times n = 0 , … , N − 1 n=0,\ldots,N-1 n = 0 , … , N − 1 , we expect the maximum expected reward V n V_n V n to be the supremum over the direct reward and the maximum expected reward at the next time step, given the best action.
In general, the second equality does not need to hold, since there might not be a a ∈ A a\in A a ∈ A , that takes the supremum value. In the case where the supremum is attained, the optimal obtained decision rules f n ∗ f_n^* f n ∗ , with
f n ∗ ( x ) ∈ argmax a ∈ A { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } , for n ∈ { 0 , … , N − 1 } , f_n^*(x)\in\operatorname{argmax}_{a\in A}\left\{\beta^n r(x,a)+\int_E V_{n+1}(x')p(dx'|x,a)\right\},\quad\text{for }n\in\{0,\ldots,N-1\}, f n ∗ ( x ) ∈ argmax a ∈ A { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } , for n ∈ { 0 , … , N − 1 } ,
do not have to be measurable.
We continue to analyse which assumptions are needed to use the Bellman equation and prove that the solutions obtained are optimal.
Theorem 2.2.3 (Verification Theorem). Let ( v n : E → [ − ∞ , ∞ ] ) n = 0 , … , N (v_n:E\to[-\infty,\infty])_{n=0,\ldots,N} ( v n : E → [ − ∞ , ∞ ] ) n = 0 , … , N be a family of measurable functions, satisfying the Bellman equation, i.e.
v N ( x ) = β N g ( x ) , v_N(x)=\beta^N g(x), v N ( x ) = β N g ( x ) , v n ( x ) = sup a ∈ A { β n r ( x , a ) + ∫ E v n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } , for n ∈ { 0 , … , N − 1 } . v_n(x)=\sup_{a\in A}\left\{\beta^n r(x,a)+\int_E v_{n+1}(x')p(dx'|x,a)\right\},\quad\text{for }n\in\{0,\ldots,N-1\}. v n ( x ) = a ∈ A sup { β n r ( x , a ) + ∫ E v n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } , for n ∈ { 0 , … , N − 1 } .
Reinforcement Learning
Then, the following holds:
For all n = 0 , … , N n=0,\ldots,N n = 0 , … , N the inequality v n ≥ V n v_n \ge V_n v n ≥ V n holds.
If a decision rule f n ∗ f_n^* f n ∗ exists such that
f n ∗ ( x ) ∈ argmax a ∈ A { β n r ( x , a ) + ∫ E v n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } , for all n ∈ { 0 , … , N − 1 } , f_n^*(x) \in\underset{a\in A}{\operatorname{argmax}}\left\{\beta^n r(x,a)+\int_E v_{n+1}(x')p(\mathrm{d}x' \mid x,a)\right\}, \qquad\text{for all }n\in\{0,\ldots,N-1\}, f n ∗ ( x ) ∈ a ∈ A argmax { β n r ( x , a ) + ∫ E v n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } , for all n ∈ { 0 , … , N − 1 } ,
then the policy π ∗ = ( f 0 ∗ , … , f N − 1 ∗ ) \pi^*=(f_0^*,\ldots,f_{N-1}^*) π ∗ = ( f 0 ∗ , … , f N − 1 ∗ ) is optimal.
Proof. We prove both statements using a backward induction argument.
For N ∈ N N\in\mathbb{N} N ∈ N , we have by definition v N = β N g ( x ) = V N v_N=\beta^N g(x)=V_N v N = β N g ( x ) = V N . Let n ∈ { 0 , … , N − 1 } n\in\{0,\ldots,N-1\} n ∈ { 0 , … , N − 1 } be arbitrary but fixed and assume that v n + 1 ≥ V n + 1 v_{n+1}\ge V_{n+1} v n + 1 ≥ V n + 1 holds. Then, for all policies π = ( f 0 , … , f N − 1 ) ∈ Ξ \pi=(f_0,\ldots,f_{N-1})\in\Xi π = ( f 0 , … , f N − 1 ) ∈ Ξ we get
v n = sup a ∈ A { β n r ( x , a ) + ∫ E v n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } ≥ sup a ∈ A { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } (induction assumption) ≥ β n r ( x , f n ( x ) ) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x ) ) = V n , π . \begin{aligned}
v_n&=\sup_{a\in A}\left\{\beta^n r(x,a)+\int_E v_{n+1}(x')p(\mathrm{d}x'\mid x,a)\right\}\\
&\ge\sup_{a\in A}\left\{\beta^n r(x,a)+\int_E V_{n+1}(x')p(\mathrm{d}x'\mid x,a)\right\} \qquad\text{(induction assumption)}\\
&\ge\beta^n r(x,f_n(x))+\int_E V_{n+1,\pi}(x')p(\mathrm{d}x'\mid x,f_n(x))=V_{n,\pi}.
\end{aligned} v n = a ∈ A sup { β n r ( x , a ) + ∫ E v n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } ≥ a ∈ A sup { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } (induction assumption) ≥ β n r ( x , f n ( x )) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x )) = V n , π .
Since v n ≥ V n , π v_n\ge V_{n,\pi} v n ≥ V n , π holds for all policies π \pi π , we get v n + 1 ≥ sup π V n , π = V n v_{n+1}\ge\sup_\pi V_{n,\pi}=V_n v n + 1 ≥ sup π V n , π = V n .
In this case, we assume that decision rules f n ∗ f_n^* f n ∗ exist with
f n ∗ ( x ) ∈ argmax a ∈ A { β n r ( x , a ) + ∫ E v n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } , for n ∈ { 0 , … , N − 1 } . f_n^*(x) \in\underset{a\in A}{\operatorname{argmax}}\left\{\beta^n r(x,a)+\int_E v_{n+1}(x')p(\mathrm{d}x'\mid x,a)\right\}, \qquad\text{for }n\in\{0,\ldots,N-1\}. f n ∗ ( x ) ∈ a ∈ A argmax { β n r ( x , a ) + ∫ E v n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } , for n ∈ { 0 , … , N − 1 } .
Using another backward induction, we prove that v n = V n = V n , π ∗ v_n=V_n=V_{n,\pi^*} v n = V n = V n , π ∗ . For the time step N N N these equalities hold by definition. Let n ∈ { 0 , … , N − 1 } n\in\{0,\ldots,N-1\} n ∈ { 0 , … , N − 1 } be arbitrary but fixed and assume that v n + 1 = V n + 1 = V n + 1 , π ∗ v_{n+1}=V_{n+1}=V_{n+1,\pi^*} v n + 1 = V n + 1 = V n + 1 , π ∗ holds. Let x ∈ E x\in E x ∈ E be arbitrary:
V n ( x ) ≤ v n ( x ) by 1 = β n r ( x , f n ∗ ( x ) ) + ∫ E v n + 1 ( x ′ ) p ( d x ′ ∣ x , f n ∗ ( x ) ) (existence assumption of f n ∗ ) = β n r ( x , f n ∗ ( x ) ) + ∫ E V n + 1 , π ∗ ( x ′ ) p ( d x ′ ∣ x , f n ∗ ( x ) ) (induction assumption) = V n , π ∗ ( x ) (Theorem 2.2.1) ≤ V n ( x ) . \begin{aligned}
V_n(x)&\le v_n(x) &&\text{by 1}\\
&=\beta^n r(x,f_n^*(x))+\int_E v_{n+1}(x')p(\mathrm{d}x'\mid x,f_n^*(x)) &&\text{(existence assumption of }f_n^*\text{)}\\
&=\beta^n r(x,f_n^*(x))+\int_E V_{n+1,\pi^*}(x')p(\mathrm{d}x'\mid x,f_n^*(x)) &&\text{(induction assumption)}\\
&=V_{n,\pi^*}(x) &&\text{(Theorem 2.2.1)}\\
&\le V_n(x).
\end{aligned} V n ( x ) ≤ v n ( x ) = β n r ( x , f n ∗ ( x )) + ∫ E v n + 1 ( x ′ ) p ( d x ′ ∣ x , f n ∗ ( x )) = β n r ( x , f n ∗ ( x )) + ∫ E V n + 1 , π ∗ ( x ′ ) p ( d x ′ ∣ x , f n ∗ ( x )) = V n , π ∗ ( x ) ≤ V n ( x ) . by 1 (existence assumption of f n ∗ ) (induction assumption) (Theorem 2.2.1)
With that we have shown that for all n ∈ { 0 , … , N } n\in\{0,\ldots,N\} n ∈ { 0 , … , N } V n = V n , π ∗ V_n=V_{n,\pi^*} V n = V n , π ∗ .
□
Remark 2.2.4. Particularly, the theorem states that if a solution of the Bellman equation exists and the functions f n ∗ f_n^* f n ∗ exist and are measurable, the resulting policy π ∗ \pi^* π ∗ is optimal. We impose conditions such that solutions of the Bellman equation exist.
Definition 2.2.5 (Structure Assumption (SAN _N N )). Let
{\mathcal M}(E) := \{v: E \to[-\infty,\infty) \mid v\text{ measurable}\}.$$ We assume that sets $\mathcal M_n \subset\mathcal M(E)$, $n \in\{0,\ldots,N\}$ exist, such that for all $n \in\{0,\ldots,N-1\}$:
1. $g_N \in\mathcal M_N$
2. If $v \in\mathcal M_{n+1}$ we assume that the following function is well-defined
E \ni x \mapsto \sup_{a}\left{\beta^n r(x,a) + \int_E v(x')p(\mathrm{d}x' \mid x,a)\right}
and in $\mathcal M_n$.
3. For all $v \in\mathcal M_{n+1}$ there exists a function $f_n:E\to A$ with
f_n(x) \in \operatorname*{argmax}_{a\in A}\left{\beta^n r(x,a) + \int_E v(x')p(\mathrm{d}x' \mid x,a)\right},
further we assume that $f_n$ is measurable.
Theorem 2.2.6 (Structure Theorem). Assume that the Structure Assumption (SAN _N N ) is fulfilled. Then, the following statements hold.
The sequence of maximal expected reward functions ( V n ) n ∈ { 0 , … , N } (V_n)_{n\in\{0,\ldots,N\}} ( V n ) n ∈ { 0 , … , N } fulfill the Bellman equation .
There exists an optimal policy π ∗ = ( f 0 ∗ , … , f N − 1 ∗ ) \pi^*=(f_0^*,\ldots,f_{N-1}^*) π ∗ = ( f 0 ∗ , … , f N − 1 ∗ ) , where for each n ∈ { 0 , … , N − 1 } n\in\{0,\ldots,N-1\} n ∈ { 0 , … , N − 1 } and x ∈ E x\in E x ∈ E the decision policy f n ∗ f_n^* f n ∗ has form
f n ∗ ( x ) ∈ argmax a ∈ A { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } . f_n^*(x) \in\operatorname*{argmax}_{a\in A}\left\{\beta^n r(x,a)+\int_E V_{n+1}(x')p(\mathrm{d}x'\mid x,a)\right\}. f n ∗ ( x ) ∈ a ∈ A argmax { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } .
Proof. We prove both statements together using a backward induction. For each n ∈ { 0 , … , N − 1 } n\in\{0,\ldots,N-1\} n ∈ { 0 , … , N − 1 } , we show that decision rules f n ∗ , … , f N − 1 ∗ f_n^*,\ldots,f_{N-1}^* f n ∗ , … , f N − 1 ∗ exist, such that for the policy π n ∗ = ( h 0 , … , h n − 1 , f n ∗ , … , f N − 1 ∗ ) ∈ Ξ \pi_n^*=(h_0,\ldots,h_{n-1},f_n^*,\ldots,f_{N-1}^*)\in\Xi π n ∗ = ( h 0 , … , h n − 1 , f n ∗ , … , f N − 1 ∗ ) ∈ Ξ , where h 0 , … , h n − 1 h_0,\ldots,h_{n-1} h 0 , … , h n − 1 are any arbitrary decision rules, for all x ∈ E x\in E x ∈ E holds
V n ( x ) = V n , π n ∗ ( x ) = sup a ∈ A { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } . V_n(x)=V_{n,\pi_n^*}(x)=\sup_{a\in A}\left\{\beta^n r(x,a)+\int_E V_{n+1}(x')p(\mathrm{d}x'\mid x,a)\right\}. V n ( x ) = V n , π n ∗ ( x ) = a ∈ A sup { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } .
Note. that for the definition of V n , π n ∗ V_{n,\pi_n^*} V n , π n ∗ only the decision rules f n ∗ , … , f N − 1 ∗ f_n^*,\ldots,f_{N-1}^* f n ∗ , … , f N − 1 ∗ are relevant, the other h 0 , … , h n − 1 h_0,\ldots,h_{n-1} h 0 , … , h n − 1 are not and we are using them to fit the definition of a policy. Further, we add to the backward induction, that for all n ∈ { 0 , … , N } n \in\{0,\ldots,N\} n ∈ { 0 , … , N } we have V n ∈ M n V_n \in\mathcal{M}_n V n ∈ M n .
We start with the backward induction.
For the time step n = N n=N n = N we got V N = g N V_N=g_N V N = g N . So by assumption ( S A N ) (\mathrm{SA}_N) ( SA N ) (i), we know that V N ∈ M N V_N \in\mathcal{M}_N V N ∈ M N .
Let n ∈ { 0 , … , N − 1 } n \in\{0,\ldots,N-1\} n ∈ { 0 , … , N − 1 } be arbitrary but fixed. We assume the following
V k ∈ M k V_k \in\mathcal{M}_k V k ∈ M k for all k ∈ { n + 1 , … , N } k \in\{n+1,\ldots,N\} k ∈ { n + 1 , … , N }
decision rules f n + 1 ∗ , … , f N − 1 ∗ f^*_{n+1},\ldots,f^*_{N-1} f n + 1 ∗ , … , f N − 1 ∗ exist, such that for all k ∈ { n + 1 , … , N − 1 } k \in\{n+1,\ldots,N-1\} k ∈ { n + 1 , … , N − 1 }
f k ∗ ( x ) ∈ argmax a ∈ A { β n r ( x , a ) + ∫ E V k + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } f^*_k(x) \in\operatorname*{argmax}_{a \in A} \left\{\beta^n r(x,a) + \int_E V_{k+1}(x')p(\mathrm{d}x' \mid x,a)\right\} f k ∗ ( x ) ∈ a ∈ A argmax { β n r ( x , a ) + ∫ E V k + 1 ( x ′ ) p ( d x ′ ∣ x , a ) }
V n + 1 , π n + 1 ∗ = V n + 1 V_{n+1,\pi^*_{n+1}}=V_{n+1} V n + 1 , π n + 1 ∗ = V n + 1 , where π n + 1 ∗ = ( h 0 , … , h n , f n + 1 ∗ , … , f N − 1 ∗ ) ∈ Ξ \pi^*_{n+1}=(h_0,\ldots,h_n,f^*_{n+1},\ldots,f^*_{N-1})\in\Xi π n + 1 ∗ = ( h 0 , … , h n , f n + 1 ∗ , … , f N − 1 ∗ ) ∈ Ξ and h 0 , … , h n h_0,\ldots,h_n h 0 , … , h n are any arbitrary decision rules
By the induction assumption 1 we get V n + 1 ∈ M n + 1 V_{n+1} \in\mathcal{M}_{n+1} V n + 1 ∈ M n + 1 . Using assumption ( S A N ) (\mathrm{SA}_N) ( SA N ) (iii), we know that for the function V n + 1 ∈ M n + 1 V_{n+1} \in\mathcal{M}_{n+1} V n + 1 ∈ M n + 1 a measurable function f n ∗ : E → A f^*_n:E\to A f n ∗ : E → A exists with
f n ∗ ( x ) ∈ argmax a ∈ A { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } , f^*_n(x) \in\operatorname*{argmax}_{a \in A} \left\{\beta^n r(x,a) + \int_E V_{n+1}(x')p(\mathrm{d}x' \mid x,a)\right\}, f n ∗ ( x ) ∈ a ∈ A argmax { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } ,
for all x ∈ E x \in E x ∈ E .
Now, consider the policy π n ∗ = ( h 0 , … , h n − 1 , f n ∗ , … , f N − 1 ∗ ) ∈ Ξ \pi^*_n=(h_0,\ldots,h_{n-1},f^*_n,\ldots,f^*_{N-1})\in\Xi π n ∗ = ( h 0 , … , h n − 1 , f n ∗ , … , f N − 1 ∗ ) ∈ Ξ , where h 0 , … , h n − 1 h_0,\ldots,h_{n-1} h 0 , … , h n − 1 are any arbitrary decision rules and f n + 1 ∗ , … , f N − 1 ∗ f^*_{n+1},\ldots,f^*_{N-1} f n + 1 ∗ , … , f N − 1 ∗ are from the induction assumption. With this policy we get for all x ∈ E x \in E x ∈ E
V n , π n ∗ ( x ) = β n r ( x , f n ∗ ( x ) ) + ∫ E V n + 1 , π n ∗ ( x ′ ) p ( d x ′ ∣ x , f n ∗ ( x ) ) (Theorem 2.2.1) = β n r ( x , f n ∗ ( x ) ) + ∫ E V n + 1 , π n + 1 ∗ ( x ′ ) p ( d x ′ ∣ x , f n ∗ ( x ) ) choose h n = f n ∗ in π n + 1 ∗ = β n r ( x , f n ∗ ( x ) ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , f n ∗ ( x ) ) (induction assumption 3) = sup a { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } . (definition of f n ∗ ) \begin{aligned}
V_{n,\pi^*_n}(x) &= \beta^n r(x,f^*_n(x))+\int_E V_{n+1,\pi^*_n}(x')p(\mathrm{d}x'\mid x,f^*_n(x)) && \text{(Theorem 2.2.1)}\\
&= \beta^n r(x,f^*_n(x))+\int_E V_{n+1,\pi^*_{n+1}}(x')p(\mathrm{d}x'\mid x,f^*_n(x)) && \text{choose }h_n=f^*_n\text{ in }\pi^*_{n+1}\\
&= \beta^n r(x,f^*_n(x))+\int_E V_{n+1}(x')p(\mathrm{d}x'\mid x,f^*_n(x)) && \text{(induction assumption 3)}\\
&= \sup_{a} \left\{\beta^n r(x,a)+\int_E V_{n+1}(x')p(\mathrm{d}x'\mid x,a)\right\}. && \text{(definition of }f^*_n\text{)}
\end{aligned} V n , π n ∗ ( x ) = β n r ( x , f n ∗ ( x )) + ∫ E V n + 1 , π n ∗ ( x ′ ) p ( d x ′ ∣ x , f n ∗ ( x )) = β n r ( x , f n ∗ ( x )) + ∫ E V n + 1 , π n + 1 ∗ ( x ′ ) p ( d x ′ ∣ x , f n ∗ ( x )) = β n r ( x , f n ∗ ( x )) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , f n ∗ ( x )) = a sup { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } . (Theorem 2.2.1) choose h n = f n ∗ in π n + 1 ∗ (induction assumption 3) (definition of f n ∗ )
With that we have
V n ( x ) ≥ sup a { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } . V_n(x)\geq\sup_{a}\left\{\beta^n r(x,a)+\int_E V_{n+1}(x')p(\mathrm{d}x'\mid x,a)\right\}. V n ( x ) ≥ a sup { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } .
On the other hand, we have for any arbitrary policy π = ( f 0 , … , f N − 1 ) ∈ Ξ \pi=(f_0,\ldots,f_{N-1})\in\Xi π = ( f 0 , … , f N − 1 ) ∈ Ξ and all x ∈ E x\in E x ∈ E
V n , π ( x ) = β n r ( x , f n ( x ) ) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x ) ) (Theorem 2.2.1) ≤ β n r ( x , f n ( x ) ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , f n ( x ) ) ≤ sup a { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } . \begin{aligned}
V_{n,\pi}(x)=\beta^n r(x,f_n(x))+\int_E V_{n+1,\pi}(x')p(\mathrm{d}x'|x,f_n(x)) \qquad\text{(Theorem 2.2.1)} \\
&\leq\beta^n r(x,f_n(x))+\int_E V_{n+1}(x')p(\mathrm{d}x'|x,f_n(x)) \\
&\leq\sup_{a}\left\{\beta^n r(x,a)+\int_E V_{n+1}(x')p(\mathrm{d}x'|x,a)\right\}.
\end{aligned} V n , π ( x ) = β n r ( x , f n ( x )) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x )) (Theorem 2.2.1) ≤ β n r ( x , f n ( x )) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , f n ( x )) ≤ a sup { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } .
Combining this inequality with the one from above and the fact that the policy π n ∗ \pi_n^* π n ∗ attains the bound, we get
V n , π n ∗ ( x ) = sup a { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } = V n ( x ) , V_{n,\pi_n^*}(x)=\sup_a\left\{\beta^n r(x,a)+\int_E V_{n+1}(x')p(\mathrm{d}x'|x,a)\right\}=V_n(x), V n , π n ∗ ( x ) = a sup { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } = V n ( x ) ,
for all x ∈ E x\in E x ∈ E . By (SAN _N N ) (ii), we now have V n ∈ M n V_n\in\mathcal{M}_n V n ∈ M n , which ends our induction. We have proven that under the Structure Assumption (SAN _N N ) the functions ( V n ) n ∈ { 0 , … , N } (V_n)_{n\in\{0,\ldots,N\}} ( V n ) n ∈ { 0 , … , N } fulfil the Bellman equation and we have shown how to calculate each V n V_n V n . □
Remark 2.2.7. Under the Structure Assumption (SAN _N N ), the Structure Theorem gives us the following algorithm, to calculate ( V n ) n ∈ { 0 , … , N } (V_n)_{n\in\{0,\ldots,N\}} ( V n ) n ∈ { 0 , … , N } and optimal policies.
Algorithm 1: Backward Induction
Data: Markov Decision Model ( E , A , p , p 0 , r , β , g ) (E,A,p,p_0,r,\beta,g) ( E , A , p , p 0 , r , β , g ) , N ∈ N N\in\mathbb{N} N ∈ N
Result: ( V n ) n ∈ { 0 , … , N } (V_n)_{n\in\{0,\ldots,N\}} ( V n ) n ∈ { 0 , … , N } and optimal policy π ∗ = ( f 0 ∗ , … , f N − 1 ∗ ) \pi^*=(f_0^*,\ldots,f_{N-1}^*) π ∗ = ( f 0 ∗ , … , f N − 1 ∗ )
V N = g V_N=g V N = g ;
for n = N − 1 , … , 0 n=N-1,\ldots,0 n = N − 1 , … , 0 do
For all x ∈ E x\in E x ∈ E calculate
V n ( x ) = sup a ∈ A { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } V_n(x)=\sup_{a\in A}\left\{\beta^n r(x,a)+\int_E V_{n+1}(x')p(\mathrm{d}x'|x,a)\right\} V n ( x ) = sup a ∈ A { β n r ( x , a ) + ∫ E V n + 1 ( x ′ ) p ( d x ′ ∣ x , a ) } ;
Calculate measurable f n ∗ f_n^* f n ∗ that takes the supremum values;
end
This algorithm works great for the calculation of the maximal expected rewards V n V_n V n , n = 0 , … , N n=0,\ldots,N n = 0 , … , N in case of A A A and E E E being finite and if the transition kernel p p p is known, as the supremum calculation for all x ∈ E x\in E x ∈ E over the action space A A A is in feasible time possible. In the next section, we see how to use the Bellman equation in case the transition kernel is unknown and in section 2.4 how to deal with uncountable sets A A A and E E E .
In the last part of this section we define the Q Q Q -functions.
Reinforcement Learning
Definition 2.2.8 (Q-function). Let π = ( f 0 , … , f N − 1 ) ∈ Ξ \pi= (f_0,\ldots,f_{N-1}) \in\Xi π = ( f 0 , … , f N − 1 ) ∈ Ξ be a policy. For all n = 0 , … , N − 1 n = 0,\ldots,N-1 n = 0 , … , N − 1 and a ∈ A a \in A a ∈ A we consider the modified policy π n , a = ( f 0 , … , f n − 1 , x ↦ a , f n + 1 , … , f N − 1 ) \pi_{n,a} = (f_0,\ldots,f_{n-1},x \mapsto a,f_{n+1},\ldots,f_{N-1}) π n , a = ( f 0 , … , f n − 1 , x ↦ a , f n + 1 , … , f N − 1 ) . We then define for all n = 0 , … , N − 1 n = 0,\ldots,N-1 n = 0 , … , N − 1 , x ∈ E x \in E x ∈ E , a ∈ A a \in A a ∈ A
Q π ( n , x , a ) = E n , x π n , a [ ∑ k = n N − 1 β k r ( X k , f k ( X k ) ) + β N g ( X N ) ] , Q^{\pi}(n,x,a) = \mathbb{E}^{\pi_{n,a}}_{n,x}\left[\sum_{k=n}^{N-1}\beta^{k}r(X_k,f_k(X_k))+\beta^{N}g(X_N)\right], Q π ( n , x , a ) = E n , x π n , a [ k = n ∑ N − 1 β k r ( X k , f k ( X k )) + β N g ( X N ) ] , and for time step n = N n = N n = N
Q π ( N , x , a ) = β N g ( x ) , Q^{\pi}(N,x,a) = \beta^{N}g(x), Q π ( N , x , a ) = β N g ( x ) , which we call the Q Q Q -function of the policy π \pi π . The optimal Q Q Q -function or action value function is given by
Q ( n , x , a ) = sup π ∈ Ξ Q π ( n , x , a ) . Q(n,x,a) = \sup_{\pi\in\Xi} Q^{\pi}(n,x,a). Q ( n , x , a ) = π ∈ Ξ sup Q π ( n , x , a ) .
Remark 2.2.9. Note that the modified policy π n , a \pi_{n,a} π n , a defined in 2.2.8 is a valid policy since the function f : E → A f:E\to A f : E → A with x ↦ a x\mapsto a x ↦ a is measurable for all a ∈ A a\in A a ∈ A and thus a decision rule. Further, the optimal Q Q Q -function is well defined by assumption A N A_N A N . Similarly as for the value function V n V_n V n , the Bellman equation holds for the Q Q Q -function:
Q ( n , x , a ) = β n r ( x , a ) + ∫ E sup a ′ ∈ A Q ( n + 1 , x ′ , a ′ ) p ( d x ′ ∣ x , a ) , Q(n,x,a)=\beta^n r(x,a)+\int_E\sup_{a'\in A}Q(n+1,x',a')p(\mathrm{d}x'\mid x,a), Q ( n , x , a ) = β n r ( x , a ) + ∫ E a ′ ∈ A sup Q ( n + 1 , x ′ , a ′ ) p ( d x ′ ∣ x , a ) ,
for all n ∈ { 0 , … , N − 1 } n\in\{0,\ldots,N-1\} n ∈ { 0 , … , N − 1 } .
Temporal Difference Learning
This section is based on the Book Reinforcement Learning: An Introduction by R. S. Sutton and A. G. Barto [4] and on the lecture notes of the course Machine Learning with Financial Applications by Prof. Dr. Knochenhauer and Dr. Bayer [5]. We show how to compute the expected total reward V n , π V_{n,\pi} V n , π for a policy π ∈ Ξ \pi\in\Xi π ∈ Ξ when the transition kernel p p p is not known.
Monte Carlo Method
One possibility to approximate the function V n , π V_{n,\pi} V n , π is to average the rewards obtained following the policy π \pi π . Let n ∈ { 0 , … , N } n \in\{0,\ldots,N\} n ∈ { 0 , … , N } and x ∈ E x \in E x ∈ E be arbitrary and assume that X 1 , … , X M X^1,\ldots,X^M X 1 , … , X M are independent realisations of the Markov Decision Process following the policy π = ( f 0 , … , f N − 1 ) \pi=(f_0,\ldots,f_{N-1}) π = ( f 0 , … , f N − 1 ) , with X n m = x X_n^m=x X n m = x for all m ∈ { 1 , … , M } m \in\{1,\ldots,M\} m ∈ { 1 , … , M } . We define
W M π ( n , x ) : = 1 M ∑ m = 1 M [ ∑ k = n N − 1 β k r ( X k m , f k ( X k m ) ) + β N g ( X N m ) ] . W_M^\pi(n,x) := \frac{1}{M}\sum_{m=1}^{M}\left[\sum_{k=n}^{N-1}\beta^k r(X_k^m,f_k(X_k^m))+\beta^N g(X_N^m)\right]. W M π ( n , x ) := M 1 m = 1 ∑ M [ k = n ∑ N − 1 β k r ( X k m , f k ( X k m )) + β N g ( X N m ) ] .
as the average returned reward starting in state x x x at time n n n and following policy π \pi π . In the case where the rewards r r r and g g g are bounded, one can show with the law of large numbers that W M π ( n , x ) → V n , π ( x ) W_M^\pi(n,x)\to V_{n,\pi}(x) W M π ( n , x ) → V n , π ( x ) for M → ∞ M\to\infty M → ∞ , in probability.
Remark 2.3.1. We make the following observation for all n ∈ { 0 , … , N } n \in\{0,\ldots,N\} n ∈ { 0 , … , N } and x ∈ E x \in E x ∈ E
W M + 1 π ( n , x ) = 1 M + 1 1 M ∑ m = 1 M + 1 [ ∑ k = n N − 1 β k r ( X k m , f k ( X k m ) ) + β N g ( X N m ) ] = 1 M + 1 [ ∑ k = n N − 1 β k r ( X k M + 1 , f k ( X k M + 1 ) ) + β N g ( X N M + 1 ) ] + 1 M + 1 1 M ∑ m = 1 M [ ∑ k = n N − 1 β k r ( X k m , f k ( X k m ) ) + β N g ( X N m ) ] = 1 M + 1 [ ∑ k = n N − 1 β k r ( X k M + 1 , f k ( X k M + 1 ) ) + β N g ( X N M + 1 ) ] + M M + 1 W M π ( n , x ) = W M π ( n , x ) + 1 M + 1 [ ( ∑ k = n N − 1 β k r ( X k M + 1 , f k ( X k M + 1 ) ) + β N g ( X N M + 1 ) ) − W M π ( n , x ) ] . \begin{aligned}
W_{M+1}^\pi(n,x)
&= \frac{1}{M+1}\frac{1}{M}\sum_{m=1}^{M+1}\left[\sum_{k=n}^{N-1}\beta^k r(X_k^m,f_k(X_k^m))+\beta^N g(X_N^m)\right] \\
&= \frac{1}{M+1}\left[\sum_{k=n}^{N-1}\beta^k r(X_k^{M+1},f_k(X_k^{M+1}))+\beta^N g(X_N^{M+1})\right] \\
&\quad+ \frac{1}{M+1}\frac{1}{M}\sum_{m=1}^{M}\left[\sum_{k=n}^{N-1}\beta^k r(X_k^m,f_k(X_k^m))+\beta^N g(X_N^m)\right] \\
&= \frac{1}{M+1}\left[\sum_{k=n}^{N-1}\beta^k r(X_k^{M+1},f_k(X_k^{M+1}))+\beta^N g(X_N^{M+1})\right] + \frac{M}{M+1}W_M^\pi(n,x) \\
&= W_M^\pi(n,x)+\frac{1}{M+1}\left[\left(\sum_{k=n}^{N-1}\beta^k r(X_k^{M+1},f_k(X_k^{M+1}))+\beta^N g(X_N^{M+1})\right)-W_M^\pi(n,x)\right].
\end{aligned} W M + 1 π ( n , x ) = M + 1 1 M 1 m = 1 ∑ M + 1 [ k = n ∑ N − 1 β k r ( X k m , f k ( X k m )) + β N g ( X N m ) ] = M + 1 1 [ k = n ∑ N − 1 β k r ( X k M + 1 , f k ( X k M + 1 )) + β N g ( X N M + 1 ) ] + M + 1 1 M 1 m = 1 ∑ M [ k = n ∑ N − 1 β k r ( X k m , f k ( X k m )) + β N g ( X N m ) ] = M + 1 1 [ k = n ∑ N − 1 β k r ( X k M + 1 , f k ( X k M + 1 )) + β N g ( X N M + 1 ) ] + M + 1 M W M π ( n , x ) = W M π ( n , x ) + M + 1 1 [ ( k = n ∑ N − 1 β k r ( X k M + 1 , f k ( X k M + 1 )) + β N g ( X N M + 1 ) ) − W M π ( n , x ) ] .
This gives us an iterative way to update the approximation W M π W_M^\pi W M π , whenever more realisations of the Markov Decision Process have been made.
Temporal Difference Learning
Temporal Difference Learning describes a similar approach to approximating the value function V n , π V_{n,\pi} V n , π as the Monte Carlo Method. It is based on the ideas shown in the proof of the reward iteration theorem 2.2.1. In the proof of theorem 2.2.1, we found that the following equality holds for all π ∈ Ξ \pi\in\Xi π ∈ Ξ , n ∈ { 0 , … , N − 1 } n \in\{0,\ldots,N-1\} n ∈ { 0 , … , N − 1 } and x ∈ E x \in E x ∈ E
V n , π ( x ) : = E n , x π [ ∑ k = n N − 1 β k r ( X k , f k ( X k ) ) + β N g ( X N ) ] = E n , x π [ β n r ( x , f n ( X n ) ) + V n + 1 , π ( X n + 1 ) ] . \begin{aligned}
V_{n,\pi}(x) := \mathbb{E}^{\pi}_{n,x}\left[\sum_{k=n}^{N-1}\beta^{k}r(X_k,f_k(X_k))+\beta^N g(X_N)\right] \\
&= \mathbb{E}^{\pi}_{n,x}\left[\beta^n r(x,f_n(X_n))+V_{n+1,\pi}(X_{n+1})\right].
\end{aligned} V n , π ( x ) := E n , x π [ k = n ∑ N − 1 β k r ( X k , f k ( X k )) + β N g ( X N ) ] = E n , x π [ β n r ( x , f n ( X n )) + V n + 1 , π ( X n + 1 ) ] .
As for the Monte Carlo method let n ∈ { 0 , … , N } n \in\{0,\ldots,N\} n ∈ { 0 , … , N } and x ∈ E x \in E x ∈ E be arbitrary and assume that X 1 , … , X M X^1,\ldots,X^M X 1 , … , X M are independent realizations of the Markov Decision Process following the policy π = ( f 0 , … , f N − 1 ) \pi=(f_0,\ldots,f_{N-1}) π = ( f 0 , … , f N − 1 ) , with X n m = x X_n^m=x X n m = x for all m ∈ { 1 , … , M } m \in\{1,\ldots,M\} m ∈ { 1 , … , M } . With that we can define an approximation to V n , π ( x ) V_{n,\pi}(x) V n , π ( x ) as
W M π ( n , x ) : = 1 M ∑ m = 1 M [ β n r ( X n m , f k ( X n m ) ) + W M π ( n + 1 , X n + 1 m ) ] , W^\pi_M(n,x):=\frac{1}{M}\sum_{m=1}^{M}\left[\beta^n r(X_n^m,f_k(X_n^m))+W^\pi_M(n+1,X_{n+1}^m)\right], W M π ( n , x ) := M 1 m = 1 ∑ M [ β n r ( X n m , f k ( X n m )) + W M π ( n + 1 , X n + 1 m ) ] ,
with W M π ( N , x ′ ) : = β N g ( x ′ ) W^\pi_M(N,x'):=\beta^N g(x') W M π ( N , x ′ ) := β N g ( x ′ ) for all x ′ ∈ E x' \in E x ′ ∈ E . As the definition depends on W M π ( n + 1 , ⋅ ) W^\pi_M(n+1,\cdot) W M π ( n + 1 , ⋅ ) the iterative update rule is given by
W M + 1 π ( n , x ) = W M π ( n , x ) + 1 M + 1 ( β n r ( x , f ( x ) ) + W M π ( n + 1 , X n + 1 M + 1 ) − W M π ( n , x ) ) . W^\pi_{M+1}(n,x)=W^\pi_M(n,x)+\frac{1}{M+1}\left(\beta^n r(x,f(x))+W^\pi_M(n+1,X_{n+1}^{M+1})-W^\pi_M(n,x)\right). W M + 1 π ( n , x ) = W M π ( n , x ) + M + 1 1 ( β n r ( x , f ( x )) + W M π ( n + 1 , X n + 1 M + 1 ) − W M π ( n , x ) ) .
Policy Improvement
In this subsection we give the idea to a fundamental concept in reinforcement learning, called policy improvement. Although, it is not directly related to Temporal Difference Learning, we decided to explain the policy improvement here, as the shown algorithms in the next section2.4 rely on this concept.
We start with the following theorem.
Theorem 2.3.2 (Policy Improvement Theorem). Let π = ( f 0 , … , f N − 1 ) \pi=(f_0,\ldots,f_{N-1}) π = ( f 0 , … , f N − 1 ) , π ′ = ( f 0 ′ , … , f N − 1 ′ ) \pi'=(f'_0,\ldots,f'_{N-1}) π ′ = ( f 0 ′ , … , f N − 1 ′ ) be two policies, such that for all x ∈ E x \in E x ∈ E and $n=0,\ldots,N
Q π ( n , x , f n ′ ( x ) ) ≥ V n , π ( x ) . Q^\pi(n,x,f'_n(x))\ge V_{n,\pi}(x). Q π ( n , x , f n ′ ( x )) ≥ V n , π ( x ) .
Then, for all x ∈ E x \in E x ∈ E and n = 0 , … , N n = 0,\ldots,N n = 0 , … , N we get
V n , π ′ ( x ) ≥ V n , π ( x ) . V_{n,\pi'}(x) \ge V_{n,\pi}(x). V n , π ′ ( x ) ≥ V n , π ( x ) .
The proof can be done in a straightforward manner, see e.g. in the book [4] section 4.2.
With this theorem, we are able to create a better policy π ′ = ( f 0 ′ , … , f N − 1 ′ ) \pi' = (f'_0,\ldots,f'_{N-1}) π ′ = ( f 0 ′ , … , f N − 1 ′ ) , where for all x ∈ E x \in E x ∈ E and n = 0 , … , N n = 0,\ldots,N n = 0 , … , N we pick
f n ′ ( x ) ∈ arg max a ∈ A Q π ( n , x , a ) . f'_n(x) \in\underset{a \in A}{\arg\max}\ Q^\pi(n,x,a). f n ′ ( x ) ∈ a ∈ A arg max Q π ( n , x , a ) .
Note that these functions f n ′ f'_n f n ′ might not be measurable anymore, thus they are invalid decision rules. As we give in this subsection only an idea on how the policy iteration works, we do not go into more detail.
With the observation that V n , π ( x ) = Q π ( n , x , f n ( x ) ) V_{n,\pi}(x) = Q^\pi(n,x,f_n(x)) V n , π ( x ) = Q π ( n , x , f n ( x )) , we immediately get that
V n , π ( x ) = Q π ( n , x , f n ( x ) ) ≤ Q π ( n , x , f n ′ ( x ) ) , V_{n,\pi}(x) = Q^\pi(n,x,f_n(x)) \le Q^\pi(n,x,f'_n(x)), V n , π ( x ) = Q π ( n , x , f n ( x )) ≤ Q π ( n , x , f n ′ ( x )) ,
thus the policy π ′ \pi' π ′ satisfies the conditions needed for the policy improvement theorem 2.3.2. Therefore, we have found a policy π ′ \pi' π ′ , such that
V n , π ′ ( x ) ≥ V n , π ( x ) , V_{n,\pi'}(x) \ge V_{n,\pi}(x), V n , π ′ ( x ) ≥ V n , π ( x ) ,
for all x ∈ E x \in E x ∈ E and n = 0 , … , N n = 0,\ldots,N n = 0 , … , N , by the policy improvement theorem 2.3.2.
We can now apply the policy improvement to the new policy π ′ \pi' π ′ and get an even better policy. In case the set of all policies Ξ \Xi Ξ is finite (if e.g. E E E , A A A are finite), this procedure will eventually give us to two policies π \pi π and π ′ \pi' π ′ , such that π = π ′ \pi= \pi' π = π ′ . In this case, we know that
V n , π ( x ) = max a ∈ A { β n r ( x , a ) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , a ) } , for n ∈ { 0 , … , N − 1 } , V_{n,\pi}(x) = \max_{a \in A} \left\{ \beta^n r(x,a) + \int_E V_{n+1,\pi}(x')p(\mathrm{d}x' \mid x,a) \right\}, \quad\text{for } n \in\{0,\ldots,N-1\}, V n , π ( x ) = a ∈ A max { β n r ( x , a ) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , a ) } , for n ∈ { 0 , … , N − 1 } ,
thus by the verification theorem 2.2.3, we get that π \pi π is optimal.
This idea is implemented in the following algorithms.
Algorithms
In this section, we see how the theoretical advances are used to establish an algorithm for finding good policies. To do this, we first present the DDPG algorithm. Then, we introduce a slight modification of the DDPG algorithm, called the TD3 algorithm, which we used in the application.
DDPG
This section is based on the paper ’Continuous control with deep reinforcement learning’, see [6].
The initial idea for the DDPG-algorithm is the following. First, assume we have a set of functions
{ Q θ Q : E × A → R ∣ θ Q ∈ R d } , \{Q_{\theta^Q}: E \times A \to\mathbb{R} \mid\theta^Q \in\mathbb{R}^d\}, { Q θ Q : E × A → R ∣ θ Q ∈ R d } ,
for some d ∈ N d \in\mathbb{N} d ∈ N , parameterised by some θ Q ∈ R d \theta^Q \in\mathbb{R}^d θ Q ∈ R d for example by using neural networks. For each θ Q \theta^Q θ Q , we consider the greedy policy π θ Q ( s ) ∈ arg max a Q θ Q ( s , a ) \pi_{\theta^Q}(s) \in\arg\max_a Q^{\theta^Q}(s,a) π θ Q ( s ) ∈ arg max a Q θ Q ( s , a ) and assume it exists. Note that this decision rule is time-independent. As the DDPG algorithm uses the same decision rule for all time steps, we use the term policy for the decision rule. In the case where time dependence is important to a problem, the current time step can be added to the state space, allowing time dependence. Our goal is to find a function approximator Q θ Q Q_{\theta^Q} Q θ Q that minimises the loss
L ( θ Q ) = E s t ∼ ρ θ Q [ ( Q θ Q ( s t , π θ Q ( s t ) ) − y θ Q , t ) 2 ] , (2) L(\theta^Q) = \mathbb{E}_{s_t \sim\rho^{\theta^Q}}\left[(Q_{\theta^Q}(s_t,\pi_{\theta^Q}(s_t)) - y_{\theta^Q,t})^2\right], \tag*{(2)} L ( θ Q ) = E s t ∼ ρ θ Q [ ( Q θ Q ( s t , π θ Q ( s t )) − y θ Q , t ) 2 ] , (2)
where ρ θ Q \rho^{\theta^Q} ρ θ Q is the state visitation distribution for the policy π θ Q \pi_{\theta^Q} π θ Q and y θ Q , t y_{\theta^Q,t} y θ Q , t is defined as
y θ Q , t : = r ( s t , π θ Q ( s t ) ) + β Q θ Q ( s t + 1 , π θ Q ( s t + 1 ) ) . y_{\theta^Q,t} := r(s_t,\pi_{\theta^Q}(s_t)) + \beta Q_{\theta^Q}(s_{t+1},\pi_{\theta^Q}(s_{t+1})). y θ Q , t := r ( s t , π θ Q ( s t )) + β Q θ Q ( s t + 1 , π θ Q ( s t + 1 )) .
We use this loss to train the Q Q Q -function to satisfy the reward iteration property 1.
In this initial idea, some steps cannot be efficiently implemented or could lead to problems. We present the solutions described in the paper [6], which result in the formulation of the DDPG-algorithm.
In the following, we point out several problems in this initial idea, show solutions that the DDPG algorithm uses and finally write down the algorithm.
We encounter the first problem in the computation of the greedy policy π θ Q \pi_{\theta^Q} π θ Q . Finding the maximising action a t a_t a t for Q θ Q ( s t , a t ) Q^{\theta^Q}(s_t,a_t) Q θ Q ( s t , a t ) for each time-step t t t is computationally expensive for uncountable action spaces. Instead, we parameterise the policy function like the Q Q Q -function and update the policy parameters to maximise the reward. Let θ π ∈ R m \theta^\pi\in\mathbb{R}^m θ π ∈ R m , for some m ∈ N m \in\mathbb{N} m ∈ N , be the parameters for functions π θ π : E → A \pi_{\theta^\pi}: E \to A π θ π : E → A , for example by using neural networks.
Let J : = E x ∼ p 0 [ V 0 , π θ π ( x ) ] J := \mathbb{E}_{x\sim p_0}[V_{0,\pi_{\theta^\pi}}(x)] J := E x ∼ p 0 [ V 0 , π θ π ( x )] . According to the paper by Silver et al. (2014) [7], the gradient of the policy performance can be written as
∇ θ π J ≈ E s t ∼ ρ θ π [ ∇ θ π Q θ Q ( s , a ) ∣ s = s t , a = π θ π ( s t ) ] = E s t ∼ ρ θ π [ ∇ a Q θ Q ( s , a ) ∣ s = s t , a = π θ π ( s t ) ∇ θ π π θ π ( s ) ∣ s = s t ] . \nabla_{\theta^\pi} J \approx\mathbb{E}_{s_t\sim\rho^{\theta^\pi}}\left[\left.\nabla_{\theta^\pi}Q_{\theta^Q}(s,a)\right|_{s=s_t,a=\pi_{\theta^\pi}(s_t)}\right]
= \mathbb{E}_{s_t\sim\rho^{\theta^\pi}}\left[\left.\nabla_aQ_{\theta^Q}(s,a)\right|_{s=s_t,a=\pi_{\theta^\pi}(s_t)}\left.\nabla_{\theta^\pi}\pi_{\theta^\pi}(s)\right|_{s=s_t}\right]. ∇ θ π J ≈ E s t ∼ ρ θ π [ ∇ θ π Q θ Q ( s , a ) ∣ s = s t , a = π θ π ( s t ) ] = E s t ∼ ρ θ π [ ∇ a Q θ Q ( s , a ) ∣ s = s t , a = π θ π ( s t ) ∇ θ π π θ π ( s ) ∣ s = s t ] .
We update the policy using this gradient, such that the update maximises the expected return from the initial distribution. The parameters θ Q \theta^Q θ Q for the Q Q Q -function are updated according to the loss L L L , see 2.1.
To compute the expectation with respect to the state visitation distribution ρ θ Q \rho^{\theta^Q} ρ θ Q , we store recent observed transitions ( s t , a t , r t , s t + 1 ) (s_t,a_t,r_t,s_{t+1}) ( s t , a t , r t , s t + 1 ) in a finite length queue called replay buffer . At each time step we uniformly sample a minibatch from the replay buffer and update the parameters θ Q \theta^Q θ Q and θ π \theta^\pi θ π . This helps to make the samples more independent and identically distributed than if they were generated by sequentially exploring the environment.
Another problem observed was that due to the definition of the loss L L L in the equation 2.1 the updates were prone to divergence, as the updated parameters θ Q \theta^Q θ Q were also part of the target y θ Q , t y_{\theta^Q,t} y θ Q , t . The proposed solution is to use copies θ Q ′ \theta^{Q'} θ Q ′ , θ π ′ \theta^{\pi'} θ π ′ of the parameters θ Q , θ π \theta^Q,\theta^\pi θ Q , θ π for the target calculation in y θ Q , t y_{\theta^Q,t} y θ Q , t in the equation 2.1. The copies θ Q ′ \theta^{Q'} θ Q ′ , θ π ′ \theta^{\pi'} θ π ′ are then updated according to the following rule
θ ′ ← τ θ + ( 1 − τ ) θ ′ , \theta' \leftarrow\tau\theta+ (1-\tau)\theta', θ ′ ← τ θ + ( 1 − τ ) θ ′ ,
for a τ ≪ 1 \tau\ll1 τ ≪ 1 , θ ∈ { θ Q , θ π } \theta\in\{\theta^Q,\theta^\pi\} θ ∈ { θ Q , θ π } and the learned parameters θ Q , θ π \theta^Q,\theta^\pi θ Q , θ π . This may slow down the learning process but increases the stability of the problem.
The final challenge is to figure out how to explore the continuous action space. The paper [6] suggests to change the policy used by adding noise from a noise process R \mathcal{R} R to the policy π θ π \pi_{\theta^\pi} π θ π . So, we use the function
π ′ ( s t ) = π θ π ( s t ) + R t \pi'(s_t)=\pi_{\theta^\pi}(s_t)+\mathcal{R}_t π ′ ( s t ) = π θ π ( s t ) + R t
to do the exploration. Note that by adding the noise, the action may no longer be within the action space A A A . Typically, clipping the action resolves this.
The choice of the noise process R \mathcal{R} R depends on the environment. Typically, the Ornstein-
Reinforcement Learning
Uhlenbeck process or the Gaussian process is used.
Algorithm 2 shows the DDPG algorithm. In the beginning, the different parameters and the replay buffer are initialised. After that, for a finite amount of episodes beginning at initial observed state s 1 s_1 s 1 , actions are made according to the current policy plus noise. These transitions are then stored in the replay buffer, from which we sample a random minibatch and update the parameters θ Q , θ π \theta^Q, \theta^\pi θ Q , θ π . Note that in the update of the Q Q Q -function, the target values y i y_i y i depend on the target parameters θ Q ′ , θ π ′ \theta^{Q\prime}, \theta^{\pi\prime} θ Q ′ , θ π ′ . These target parameters are then updated in the last step according to the update rule θ ′ ← τ θ + ( 1 − τ ) θ ′ \theta^\prime\leftarrow\tau\theta+ (1-\tau)\theta^\prime θ ′ ← τ θ + ( 1 − τ ) θ ′ , for θ ∈ { θ Q , θ π } \theta\in\{\theta^Q,\theta^\pi\} θ ∈ { θ Q , θ π } .
Algorithm 2: DDPG algorithm
Randomly initialise Q-network Q θ Q ( s , a ) Q^{\theta^Q}(s,a) Q θ Q ( s , a ) and policy π θ π ( s ) \pi^{\theta^\pi}(s) π θ π ( s ) with parameters θ Q , θ π \theta^Q,\theta^\pi θ Q , θ π .
Initialise target parameters with θ Q ′ ← θ Q \theta^{Q\prime} \leftarrow\theta^Q θ Q ′ ← θ Q , θ π ′ ← θ π \theta^{\pi\prime} \leftarrow\theta^\pi θ π ′ ← θ π .
Initialise replay buffer R \mathcal{R} R .
for e p i s o d e = 1 , … , M episode = 1,\ldots,M e p i so d e = 1 , … , M do
Initialise random process R \mathcal{R} R for action exploration.
Receive initial observation state s 1 s_1 s 1 .
for t = 1 , … , N t=1,\ldots,N t = 1 , … , N do
Select action a t = π π ( s t ) + R t a_t = \pi^{\pi}(s_t) + \mathcal{R}_t a t = π π ( s t ) + R t
Execute action a t a_t a t , observe reward r t r_t r t and new state s t + 1 s_{t+1} s t + 1 .
Store transition ( s t , a t , r t , s t + 1 ) (s_t,a_t,r_t,s_{t+1}) ( s t , a t , r t , s t + 1 ) in R \mathcal{R} R
Sample random minibatch of K K K transitions ( s i , a i , r i , s i + 1 ) (s_i,a_i,r_i,s_{i+1}) ( s i , a i , r i , s i + 1 ) from R \mathcal{R} R
Set y i = r i + β Q θ Q ( s i + 1 , π θ π ( s i + 1 ) ) y_i = r_i + \beta Q^{\theta^{Q}}(s_{i+1},\pi^{\theta^\pi}(s_{i+1})) y i = r i + β Q θ Q ( s i + 1 , π θ π ( s i + 1 ))
Update Q Q Q -function parameters θ Q \theta^Q θ Q , minimising L = 1 K ∑ i ( y i − Q θ Q ( s i , a i ) ) 2 L = \frac{1}{K}\sum_i(y_i-Q^{\theta^Q}(s_i,a_i))^2 L = K 1 ∑ i ( y i − Q θ Q ( s i , a i ) ) 2
Update policy parameters using the sampled policy gradient
∇ θ π J ≈ 1 K ∑ i ∇ a Q θ Q ( s , a ) ∣ s = s i , a = π θ π ( s i ) ∇ θ π π θ π ( s ) ∣ s = s i \nabla_{\theta^\pi} J \approx\frac{1}{K}\sum_i \nabla_a Q^{\theta^Q}(s,a)\vert_{s=s_i,a=\pi^{\theta^\pi}(s_i)}\nabla_{\theta^\pi}\pi^{\theta^\pi}(s)\vert_{s=s_i} ∇ θ π J ≈ K 1 i ∑ ∇ a Q θ Q ( s , a ) ∣ s = s i , a = π θ π ( s i ) ∇ θ π π θ π ( s ) ∣ s = s i
Update target networks
θ ′ ← τ θ + ( 1 − τ ) θ ′ , for θ ∈ { θ Q , θ π } \theta^\prime\leftarrow\tau\theta+ (1-\tau)\theta^\prime,\quad\text{for }\theta\in\{\theta^Q,\theta^\pi\} θ ′ ← τ θ + ( 1 − τ ) θ ′ , for θ ∈ { θ Q , θ π }
end
end
We see that the DDPG algorithm depends on many parameters that need to be chosen. To begin with, there are structure parameters for the Q Q Q and policy network, which are typically deep neural networks, further, parameters for the size of the replay buffer, for the random noise process R \mathcal{R} R , learning rates for the Q Q Q -function and policy updates and at last the parameter τ \tau τ . The performance of the DDPG algorithm strongly depends on those so called hyperparameters. Thus, in section 2.6, we investigate how to efficiently find good hyperparameters.
TD3
In this subsection, we introduce the Twin Delayed Deep Deterministic policy gradient algorithm, in short TD3 algorithm, which is an extension of the DDPG algorithm. The subsection is based on the paper ’Addressing Function Approximation Error in Actor-Critic Methods ’ by S. Fukumoto, H. van Hoof and D. Meger [8]. In this paper, the use of target networks is linked to the overestimation of the Q Q Q -function, a common problem in value-based reinforcement learning methods, like in the DDPG algorithm. Here we show the improvements they suggest and the resulting algorithm.
In the paper ’Issues in Using Function Approximation for Reinforcement Learning ’ by S. Thrun and A. Schwartz [9], it is shown that if the value estimates are updated with a greedy target y = r + β max a ′ Q ( s ′ , a ′ ) y = r + \beta\max_{a'} Q(s', a') y = r + β max a ′ Q ( s ′ , a ′ ) and the target is susceptible to some mean-zero error ϵ \epsilon ϵ then the value with the error will, in general, be greater than the true maximum, as E ϵ [ max a ′ ( Q ( s ′ , a ′ ) + ϵ ) ] ≥ max a ′ Q ( s ′ , a ′ ) \mathbb{E}_{\epsilon}[\max_{a'}(Q(s', a') + \epsilon)] \geq\max_{a'} Q(s', a') E ϵ [ max a ′ ( Q ( s ′ , a ′ ) + ϵ )] ≥ max a ′ Q ( s ′ , a ′ ) . This overestimation is then propagated through the Bellman equation to the whole Q Q Q -function. Although, in the DDPG algorithm, the value updates aren’t directly updated with a greedy target, the presence of the overestimation bias is still given, as shown in experiments in (Fukumoto, van Hoof and D. Meger, 2018) [8].
As this problem is induced by the function approximators, it is unavoidable. The following changes were made in the DDPG algorithm to try to minimise the impact.
The first improvement is to train 2 different Q Q Q -functions, instead of one. This will give us 2 separate value estimates. We then take the smaller value in the target computation y i y_i y i and use that value to update both Q Q Q -functions. To be more precise, 2 random Q Q Q -value parameters θ 1 , θ 2 \theta_1,\theta_2 θ 1 , θ 2 will be initialised at the beginning. For a transition ( s t , a t , r t , s t + 1 ) (s_t, a_t, r_t, s_{t+1}) ( s t , a t , r t , s t + 1 ) from the replay buffer R \mathcal{R} R , we calculate the target value y y y as y = r t + β min j = 1 , 2 Q θ j ( s t + 1 , π θ π ( s t ) ) y = r_t + \beta\min_{j=1,2} Q^{\theta_j}(s_{t+1}, \pi^{\theta^\pi}(s_t)) y = r t + β min j = 1 , 2 Q θ j ( s t + 1 , π θ π ( s t )) and update the parameters θ 1 , θ 2 \theta_1,\theta_2 θ 1 , θ 2 to minimise ( y − Q θ j ( s t , a t ) ) 2 (y - Q^{\theta_j}(s_t, a_t))^2 ( y − Q θ j ( s t , a t ) ) 2 for j = 1 , 2 j = 1, 2 j = 1 , 2 .
The next change is that the updates for the policy parameters θ π \theta^\pi θ π and target networks will only be executed after a fixed number d ∈ N d \in\mathbb{N} d ∈ N of updates on the Q Q Q -function parameters θ 1 , θ 2 \theta_1,\theta_2 θ 1 , θ 2 . The reason for this change is to reduce the likelihood of repeatedly updating the policy and target parameters in the case where the Q Q Q -function parameters do not change. This lowers the variance of the value estimates for the policy updates, and thus improves the quality of the policy updates.
The last change is in regard of the concern that the policy may overfit in the value estimate. The updates on the Q Q Q -function are highly affected by the function approximation errors if the learned target is using a deterministic policy, which increases the variance of the target. In order to reduce the variance, a regularisation term has been introduced. The target y y y is calculated for a transition ( s t , a t , r t , s t + 1 ) (s_t, a_t, r_t, s_{t+1}) ( s t , a t , r t , s t + 1 ) as
y = r t + β min j = 1 , 2 Q θ j ′ ( s t + 1 , π θ ′ ( s t ) + ϵ ) y = r_t + \beta\min_{j=1,2} Q^{\theta'_j}\left(s_{t+1}, \pi^{\theta'}(s_t) + \epsilon\right) y = r t + β j = 1 , 2 min Q θ j ′ ( s t + 1 , π θ ′ ( s t ) + ϵ )
where ϵ ∼ clip ( N ( 0 , σ ) , − c , c ) \epsilon\sim\operatorname{clip}(\mathcal{N}(0,\sigma),-c,c) ϵ ∼ clip ( N ( 0 , σ ) , − c , c ) , for some hyperparameters σ , c \sigma,c σ , c and N \mathcal{N} N is the normal distribution and clip is a clipping operator. The clipping has been added, such that the target remains close to the original action.
In the paper introducing the TD3 algorithm [8], they set the noise process R \mathcal{R} R as the normal distribution N ( 0 , σ ) \mathcal{N}(0,\sigma) N ( 0 , σ ) . We change that and allow any noise process, such that it can be fitted to the problem. Further, we make a small modification at the initialisation process of the replay buffer R \mathcal{R} R . For a finite number of runs L L L , we add transitions to the replay buffer, using a uniform random policy, allowing transitions to be in the replay buffer from the start.
The TD3 algorithm is then given by
Algorithm 3: TD3 algorithm
Randomly initialise Q Q Q -networks Q θ 1 Q^{\theta_1} Q θ 1 , Q θ 2 Q^{\theta_2} Q θ 2 and policy π θ π \pi^{\theta^\pi} π θ π with parameters θ 1 , θ 2 , θ π \theta_1,\theta_2,\theta^\pi θ 1 , θ 2 , θ π .
Initialise target parameters with θ j ′ ← θ j \theta'_j \leftarrow\theta_j θ j ′ ← θ j , for j = 1 , 2 j=1,2 j = 1 , 2 , θ ′ π ← θ π \theta'^\pi\leftarrow\theta^\pi θ ′ π ← θ π .
Initialise replay buffer R R R . Add L L L runs of uniform random transitions to R R R .
for episode = 1 , … , M =1,\ldots,M = 1 , … , M do
Initialise random process R \mathcal{R} R for action exploration.
Receive initial observation state s 1 s_1 s 1 .
for t = 1 , … , N t=1,\ldots,N t = 1 , … , N do
Select action a t = π θ π ( s t ) + R t a_t=\pi^{\theta^\pi}(s_t)+\mathcal{R}_t a t = π θ π ( s t ) + R t
Execute action a t a_t a t , observe reward r t r_t r t and new state s t + 1 s_{t+1} s t + 1 .
Store transition ( s t , a t , r t , s t + 1 ) (s_t,a_t,r_t,s_{t+1}) ( s t , a t , r t , s t + 1 ) in R R R
Sample random minibatch of K K K transitions ( s i , a i , r i , s i + 1 ) (s_i,a_i,r_i,s_{i+1}) ( s i , a i , r i , s i + 1 ) from R R R
Define a ~ i ← π θ ′ π + ϵ \tilde{a}_i\leftarrow\pi^{\theta'^\pi}+\epsilon a ~ i ← π θ ′ π + ϵ , where ϵ ∼ clip ( N ( 0 , σ ) , − c , c ) \epsilon\sim\operatorname{clip}(\mathcal{N}(0,\sigma),-c,c) ϵ ∼ clip ( N ( 0 , σ ) , − c , c )
Set y i = r i + β min j = 1 , 2 Q θ j ′ ( s i + 1 , a ~ i ) y_i=r_i+\beta\min_{j=1,2}Q^{\theta'_j}(s_{i+1},\tilde{a}_i) y i = r i + β min j = 1 , 2 Q θ j ′ ( s i + 1 , a ~ i )
Update Q Q Q -function parameters θ j \theta_j θ j , minimising L = 1 K ∑ i ( y i − Q θ j ( s i , a i ) ) 2 L=\frac{1}{K}\sum_i(y_i-Q^{\theta_j}(s_i,a_i))^2 L = K 1 ∑ i ( y i − Q θ j ( s i , a i ) ) 2 , for j = 1 , 2 j=1,2 j = 1 , 2
if t m o d d t\bmod d t mod d then
Update policy parameters using the sampled policy gradient
∇ θ π J ≈ 1 K ∑ i ∇ a Q θ 1 ( s , a ) ∣ s = s i , a = π θ π ( s i ) ∇ θ π π θ π ( s ) ∣ s = s i \nabla_{\theta^\pi}J\approx\frac{1}{K}\sum_i\nabla_a Q^{\theta_1}(s,a)\big|_{s=s_i,a=\pi^{\theta^\pi}(s_i)}\nabla_{\theta^\pi}\pi^{\theta^\pi}(s)\big|_{s=s_i} ∇ θ π J ≈ K 1 i ∑ ∇ a Q θ 1 ( s , a ) s = s i , a = π θ π ( s i ) ∇ θ π π θ π ( s ) s = s i
Update target networks
θ ′ ← τ θ + ( 1 − τ ) θ ′ , for θ ∈ { θ 1 , θ 2 , θ π } \theta'\leftarrow\tau\theta+(1-\tau)\theta',\quad\text{for }\theta\in\{\theta_1,\theta_2,\theta^\pi\} θ ′ ← τ θ + ( 1 − τ ) θ ′ , for θ ∈ { θ 1 , θ 2 , θ π }
end
end
end
Note that our TD3 algorithm implantation has even more hyperparameters than the DDPG algorithm. In total we have the following hyperparameters: shape Q Q Q -networks, policy networks, size replay buffer, amount of start runs L L L , number of episodes M M M , random process R \mathcal{R} R , size of minibatches K K K , clipping parameter c c c and the number d ∈ N d\in\mathbb{N} d ∈ N .
In some applications the discount factor β \beta β can be seen as a hyperparameter. For example, in cases where a Markov Decision Model has the discount factor β = 1 \beta=1 β = 1 , one could change the discount factor in the algorithm and possibly get better results using the new discount factor.
Neural Networks
This subsection provides a brief introduction to neural networks. It is based on the book Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David [10] and on my Bachelor’s thesis [11].
Reinforcement learning algorithms use neural networks as approximators for the Q Q Q -function and policy. They are exceptionally useful due to their capacity for flexible adjustment of their complexity. Moreover, it can be shown that neural networks are able to approximate any continuous function up to any ε > 0 \varepsilon> 0 ε > 0 , see 2.4.3.
Definition 2.4.1 (Neural Networks). Let X ⊆ R d 1 X \subseteq\mathbb{R}^{d_1} X ⊆ R d 1 be the input space and Y ⊆ R d n + 1 Y \subseteq\mathbb{R}^{d_{n+1}} Y ⊆ R d n + 1 the output space for some d 1 , d n + 1 ∈ N d_1,d_{n+1} \in\mathbb{N} d 1 , d n + 1 ∈ N , of a function which we want to approximate.
Neural networks are a composition of functions Φ ( 1 ) , … , Φ ( n ) \Phi^{(1)}, \ldots, \Phi^{(n)} Φ ( 1 ) , … , Φ ( n ) , where each Φ ( i ) : R d i → R d i + 1 \Phi^{(i)}: \mathbb{R}^{d_i} \to\mathbb{R}^{d_{i+1}} Φ ( i ) : R d i → R d i + 1 , d i , d i + 1 ∈ N d_i,d_{i+1} \in\mathbb{N} d i , d i + 1 ∈ N , for i ∈ { 1 , … , n } i \in\{1,\ldots,n\} i ∈ { 1 , … , n } , i.e.
Φ ( x ) = Φ ( n ) ( ⋯ ( Φ ( 1 ) ( x ) ) ⋯ ) , \Phi(x) = \Phi^{(n)}(\cdots(\Phi^{(1)}(x))\cdots), Φ ( x ) = Φ ( n ) ( ⋯ ( Φ ( 1 ) ( x )) ⋯ ) , where for i = 1 , … , n − 1 i = 1,\ldots,n-1 i = 1 , … , n − 1 the function Φ ( i ) \Phi^{(i)} Φ ( i ) has the structure:
Φ ( i ) ( x ) = ψ ( W ( i ) x + b ( i ) ) , \Phi^{(i)}(x) = \psi(W^{(i)}x + b^{(i)}), Φ ( i ) ( x ) = ψ ( W ( i ) x + b ( i ) ) , and Φ ( n ) \Phi^{(n)} Φ ( n ) has the form
Φ ( n ) ( x ) = W ( n ) x + b ( n ) , \Phi^{(n)}(x) = W^{(n)}x + b^{(n)}, Φ ( n ) ( x ) = W ( n ) x + b ( n ) , for a non-linear function ψ : R → R \psi: \mathbb{R} \to\mathbb{R} ψ : R → R , that is applied component wise, W ( i ) ∈ R d i + 1 × d i W^{(i)} \in\mathbb{R}^{d_{i+1} \times d_i} W ( i ) ∈ R d i + 1 × d i and b ( i ) ∈ R d i + 1 b^{(i)} \in\mathbb{R}^{d_{i+1}} b ( i ) ∈ R d i + 1 .
The function ψ \psi ψ is called the activation function, W ( i ) W^{(i)} W ( i ) the weight matrix and b ( i ) b^{(i)} b ( i ) the bias and define W : = ( W ( 1 ) , … , W ( n ) ) W := (W^{(1)},\ldots,W^{(n)}) W := ( W ( 1 ) , … , W ( n ) ) and b : = ( b ( 1 ) , … , b ( n ) ) b := (b^{(1)},\ldots,b^{(n)}) b := ( b ( 1 ) , … , b ( n ) ) . The number n n n is called the number of hidden layers and for all i ∈ { 1 , … , n } i \in\{1,\ldots,n\} i ∈ { 1 , … , n } the number d i d_i d i is called the number of nodes in the hidden layer i i i .
Choosing the right number of hidden layers and nodes within each hidden layer is not an easy task and is highly dependent on the given problem. Therefore, in the Hyperparameter search section 2.6, we show how to efficiently find good hyperparameters.
In our further analysis, we use the non-linear activation function called *rectified linear unit (ReLU), which is defined as
ψ r e l u ( x ) : = { x if x > 0 0 else \psi_{\mathrm{relu}}(x) :=
\begin{cases}
x & \text{if } x > 0 \\
0 & \text{else}
\end{cases} ψ relu ( x ) := { x 0 if x > 0 else
The following theorem shows us that any continuous function can be approximated by neural networks.
Theorem 2.4.3 (General Approximation Theorem, by [12]). Let K ⊆ R d 1 K \subseteq\mathbb{R}^{d_1} K ⊆ R d 1 be compact and let ψ : R → R \psi: \mathbb{R} \to\mathbb{R} ψ : R → R be an activation function, that is continuous and non-polynomial. Then, the set of functions representable by a neural network with a single hidden layer and activation function ψ \psi ψ is dense in the space of continuous functions f : K → R d n + 1 f: K \to\mathbb{R}^{d_{n+1}} f : K → R d n + 1 in the topology of uniform convergence. I.e. for all continuous function f : K → R d n + 1 f: K \to\mathbb{R}^{d_{n+1}} f : K → R d n + 1 and ε > 0 \varepsilon> 0 ε > 0 there exists a neural network Φ \Phi Φ , with depth 1, s.t.
sup x ∈ K ∥ Φ ( x ) − f ( x ) ∥ < ε . \sup_{x \in K} \lVert\Phi(x) - f(x) \rVert< \varepsilon. x ∈ K sup ∥ Φ ( x ) − f ( x )∥ < ε .
The proof can be read in the book Mathematical foundations of supervised learning by M. Wolf [12] (see Theorem 2.7 in the book). Note that the ReLU activation function is continuous and non-polynomial.
Now, we define another type of neural networks called convolutional neural networks. They are typically used, when 2D arrays are given as input. One could flatten the input spaces, but for some 2D array inputs, like pictures, the information of pixels next to each other might get lost. We have used them in our application to encode a histogram plot of the electrons to a 4-dimensional vector, that gives us information about the shape of the electrons in the histogram plot. The following part is based on [13].
Definition 2.4.4 (Convolutional neural networks). Let X ⊆ R d 1 , d 1 ′ X \subseteq\mathbb{R}^{d_1,d'_1} X ⊆ R d 1 , d 1 ′ be the input-space and Y ⊆ R d n + 1 Y \subseteq\mathbb{R}^{d_{n+1}} Y ⊆ R d n + 1 the output space for some d 1 , d 1 ′ , d n + 1 ∈ N d_1,d'_1,d_{n+1} \in\mathbb{N} d 1 , d 1 ′ , d n + 1 ∈ N , which we want to approximate.
Convolutional neural networks are a composition of functions Φ ( 1 ) , … , Φ ( n ) \Phi^{(1)}, \ldots, \Phi^{(n)} Φ ( 1 ) , … , Φ ( n ) , where each Φ ( i ) : R d i , d i ′ → R d i + 1 , d i + 1 ′ \Phi^{(i)}: \mathbb{R}^{d_i,d'_i} \to\mathbb{R}^{d_{i+1},d'_{i+1}} Φ ( i ) : R d i , d i ′ → R d i + 1 , d i + 1 ′ , d i , d i ′ , d i + 1 , d i + 1 ′ ∈ N d_i,d'_i,d_{i+1},d'_{i+1} \in\mathbb{N} d i , d i ′ , d i + 1 , d i + 1 ′ ∈ N , for i ∈ { 1 , … , n − 1 } i \in\{1,\ldots,n-1\} i ∈ { 1 , … , n − 1 } and Φ ( n ) : R d n , d n ′ → R d n − 1 ⋅ d n − 1 ′ \Phi^{(n)}: \mathbb{R}^{d_n,d'_n} \to\mathbb{R}^{d_{n-1}\cdot d'_{n-1}} Φ ( n ) : R d n , d n ′ → R d n − 1 ⋅ d n − 1 ′ , i.e.
Φ ( x ) = Φ ( n ) ( ⋯ ( Φ ( 1 ) ( x ) ) ⋯ ) , \Phi(x) = \Phi^{(n)}(\cdots(\Phi^{(1)}(x))\cdots), Φ ( x ) = Φ ( n ) ( ⋯ ( Φ ( 1 ) ( x )) ⋯ ) ,
Reinforcement Learning
where Φ ( n ) \Phi^{(n)} Φ ( n ) flattens/vectorises 2D arrays into vectors.
For all other Φ ( i ) \Phi^{(i)} Φ ( i ) , one of the following description holds
(activation layer) For a non-linear function ψ : R → R \psi:\mathbb{R} \to\mathbb{R} ψ : R → R , the function Φ ( i ) : R d i , d i ′ → R d i , d i ′ \Phi^{(i)}:\mathbb{R}^{d_i,d_i'} \to\mathbb{R}^{d_i,d_i'} Φ ( i ) : R d i , d i ′ → R d i , d i ′ is the function, that applies the non-linear function component wise
(max pooling layer) Let A = ( A i , j ) ∈ R d i , d i ′ A=(A_{i,j})\in\mathbb{R}^{d_i,d_i'} A = ( A i , j ) ∈ R d i , d i ′ . For stride lengths s , s ′ ∈ N s,s'\in\mathbb{N} s , s ′ ∈ N and a window size ( p + 1 ) × ( p ′ + 1 ) (p+1)\times(p'+1) ( p + 1 ) × ( p ′ + 1 ) , where p , p ′ p,p' p , p ′ both are even, the output Φ ( i ) ( A ) = A ~ ∈ R d i − 2 s , d i ′ − 2 s ′ \Phi^{(i)}(A)=\widetilde{A}\in\mathbb{R}^{d_i-2s,d_i'-2s'} Φ ( i ) ( A ) = A ∈ R d i − 2 s , d i ′ − 2 s ′ is given by the following rule for all i ∈ { s + 1 , … , d i − s } i\in\{s+1,\ldots,d_i-s\} i ∈ { s + 1 , … , d i − s } and j ∈ { s ′ + 1 , … , d i ′ − s ′ } j\in\{s'+1,\ldots,d_i'-s'\} j ∈ { s ′ + 1 , … , d i ′ − s ′ }
A ~ i − s , j − s ′ = max { A k , l ∣ k ∈ { i − p 2 , … , i + p 2 } , l ∈ { j − p ′ 2 , … , j + p ′ 2 } } , \widetilde{A}_{i-s,j-s'}=\max\{A_{k,l}\mid k\in\{i-\frac{p}{2},\ldots,i+\frac{p}{2}\},l\in\{j-\frac{p'}{2},\ldots,j+\frac{p'}{2}\}\}, A i − s , j − s ′ = max { A k , l ∣ k ∈ { i − 2 p , … , i + 2 p } , l ∈ { j − 2 p ′ , … , j + 2 p ′ }} ,
where in case the window leaves the matrix A A A , all non-defined A k , l A_{k,l} A k , l are set to − ∞ -\infty − ∞ .
In example 2.4.5 we see the function in more detail.
(convolutional layer) Let A = ( A i , j ) ∈ R d i , d i ′ A=(A_{i,j})\in\mathbb{R}^{d_i,d_i'} A = ( A i , j ) ∈ R d i , d i ′ . For stride lengths s , s ′ ∈ N s,s'\in\mathbb{N} s , s ′ ∈ N , a window size ( p + 1 ) × ( p ′ + 1 ) (p+1)\times(p'+1) ( p + 1 ) × ( p ′ + 1 ) , where p , p ′ p,p' p , p ′ both are even, a weight matrix W ∈ R p + 1 , p ′ + 1 W\in\mathbb{R}^{p+1,p'+1} W ∈ R p + 1 , p ′ + 1 an bias b ∈ R b\in\mathbb{R} b ∈ R the output Φ ( i ) ( A ) = A ~ ∈ R d i − 2 s , d i ′ − 2 s ′ \Phi^{(i)}(A)=\widetilde{A}\in\mathbb{R}^{d_i-2s,d_i'-2s'} Φ ( i ) ( A ) = A ∈ R d i − 2 s , d i ′ − 2 s ′ is given by the following rule for all i ∈ { s + 1 , … , d i − s } i\in\{s+1,\ldots,d_i-s\} i ∈ { s + 1 , … , d i − s } and j ∈ { s ′ + 1 , … , d i ′ − s ′ } j\in\{s'+1,\ldots,d_i'-s'\} j ∈ { s ′ + 1 , … , d i ′ − s ′ }
A ~ i − s , j − s ′ = b + ∑ { A k , l ⋅ W k − ( i − p 2 ) + 1 , l − ( j − p ′ 2 ) + 1 ∣ k ∈ { i − p 2 , … , i + p 2 } , \widetilde{A}_{i-s,j-s'}=b+\sum\{A_{k,l}\cdot W_{k-(i-\frac{p}{2})+1,l-(j-\frac{p'}{2})+1}\mid k\in\{i-\frac{p}{2},\ldots,i+\frac{p}{2}\}, A i − s , j − s ′ = b + ∑ { A k , l ⋅ W k − ( i − 2 p ) + 1 , l − ( j − 2 p ′ ) + 1 ∣ k ∈ { i − 2 p , … , i + 2 p } ,
l ∈ { j − p ′ 2 , … , j + p ′ 2 } } , l\in\{j-\frac{p'}{2},\ldots,j+\frac{p'}{2}\}\}, l ∈ { j − 2 p ′ , … , j + 2 p ′ }} ,
where in case the window leaves the matrix A A A , all non-defined A k , l A_{k,l} A k , l are set to 0.
As above, we see the convolution layer in more detail in the following example 2.4.5.
We extend the definition by considering not one, but multiple weight matrices within one convolutional layer. The output is then in the space R c × R d i − 2 s , d i ′ − 2 s ′ \mathbb{R}^{c}\times\mathbb{R}^{d_i-2s,d_i'-2s'} R c × R d i − 2 s , d i ′ − 2 s ′ , where c c c is the amount of weight matrices used, called the number of channels. Each weight matrix gets its own dimension. If the next layer gets such an 3-dimensional array as input, the activation layer remains to be defined component wise, the max pooling layer uses the 2 dimensional window on all channels and for a convolutional layer with number of channels c ~ \tilde{c} c ~ , the convolution of a weight matrix is done over all input channels and then summed up.
Example 2.4.5. Consider the matrix
A = ( 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 6 7 8 9 10 1 2 3 4 5 ) . A = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
6 & 7 & 8 & 9 & 10 \\
11 & 12 & 13 & 14 & 15 \\
6 & 7 & 8 & 9 & 10 \\
1 & 2 & 3 & 4 & 5
\end{pmatrix}. A = 1 6 11 6 1 2 7 12 7 2 3 8 13 8 3 4 9 14 9 4 5 10 15 10 5 . For stride lengths s , s ′ = 1 s, s' = 1 s , s ′ = 1 , window size (3, 3), the max pooling layer returns the following matrix
A ~ = ( 13 14 15 13 14 15 13 14 15 ) . \widetilde{A} = \begin{pmatrix}
13 & 14 & 15 \\
13 & 14 & 15 \\
13 & 14 & 15
\end{pmatrix}. A = 13 13 13 14 14 14 15 15 15 . For the same stride lengths and window size, we get with the weight matrix
W = ( 1 1 1 0 0 0 − 1 − 1 − 1 ) W = \begin{pmatrix}
1 & 1 & 1 \\
0 & 0 & 0 \\
-1 & -1 & -1
\end{pmatrix} W = 1 0 − 1 1 0 − 1 1 0 − 1 and bias b = 0 b = 0 b = 0 , the following output after a convolution layer with weights W W W
A ~ = ( − 30 − 30 − 30 0 0 0 30 30 30 ) . \widetilde{A} = \begin{pmatrix}
-30 & -30 & -30 \\
0 & 0 & 0 \\
30 & 30 & 30
\end{pmatrix}. A = − 30 0 30 − 30 0 30 − 30 0 30 .
Partially Observable Markov Decision Processes
In our application, the data which we are able to access is only a part of the underlying Markov Decision Process. Instead of the information on all electrons, we are only able to access accumulations (histogram plots) via sensors. Therefore, we can not observe the whole state space E E E , but an observable part. In this section we introduce partially observable Markov Decision Processes and connect them to Markov Decision Processes. The section is based on the book Markov decision processes with applications to finance [3] by Nicole Bäuerle and Ulrich Rieder.
Definition 2.5.1 (Partially Observable Markov Decision Model). We call a tuple ( E X × E Y , A , p , p 0 , r , β , g ) (E_X \times E_Y, A, p, p_0, r, \beta, g) ( E X × E Y , A , p , p 0 , r , β , g ) a partially observable Markov Decision Model, where
E X × E Y E_X \times E_Y E X × E Y is called state space. We assume that E X ⊆ R m E_X \subseteq\mathbb{R}^{m} E X ⊆ R m and E Y ⊆ R n E_Y \subseteq\mathbb{R}^{n} E Y ⊆ R n , for some m , n ∈ N m,n \in\mathbb{N} m , n ∈ N equipped with the Borel σ \sigma σ -algebras E X , E Y \mathcal{E}_X,\mathcal{E}_Y E X , E Y . For ( x , y ) ∈ E X × E Y (x,y) \in E_X \times E_Y ( x , y ) ∈ E X × E Y we call x x x the observable component of the state and y y y the part that cannot be observed
A A A is a measurable space with σ \sigma σ -algebra A \mathcal{A} A , called state space
p p p is a stochastic transition kernel from E X × E Y × A E_X \times E_Y \times A E X × E Y × A to E X × E Y E_X \times E_Y E X × E Y , i.e. for all ( x , y , a ) ∈ E X × E Y × A (x,y,a) \in E_X \times E_Y \times A ( x , y , a ) ∈ E X × E Y × A and Borel sets B ∈ E X ⊗ E Y B \in\mathcal{E}_X \otimes\mathcal{E}_Y B ∈ E X ⊗ E Y the function ( x , y , a ) ↦ p ( B ∣ x , y , a ) (x,y,a) \mapsto p(B \mid x,y,a) ( x , y , a ) ↦ p ( B ∣ x , y , a ) is a probability measure on E X ⊗ E Y \mathcal{E}_X \otimes\mathcal{E}_Y E X ⊗ E Y and the mapping ( x , y , a ) ↦ p ( B ∣ x , y , a ) (x,y,a) \mapsto p(B \mid x,y,a) ( x , y , a ) ↦ p ( B ∣ x , y , a ) is measurable. The value p ( B ∣ x , y , a ) p(B \mid x,y,a) p ( B ∣ x , y , a ) is interpreted as probability of set B B B given current state ( x , y ) ∈ E X × E Y (x,y) \in E_X \times E_Y ( x , y ) ∈ E X × E Y and chosen action a ∈ A a \in A a ∈ A .
p 0 p_0 p 0 is called initial probability on Y Y Y
r : E X × E Y × A → R r : E_X \times E_Y \times A \to\mathbb{R} r : E X × E Y × A → R measurable function called reward function
discount factor β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ]
g : E X × E Y → R g : E_X \times E_Y \to\mathbb{R} g : E X × E Y → R measurable function, called terminal reward function
The definition of a partially observable Markov decision model is similar to the definition of a Markov decision model. The main difference is that we distinguish between an observable and an unobservable part.
We now define policies. In contrast to the book [3], where policies can take into account the entire observable history up to that point, we define policies π \pi π as a sequence of decision rules π = ( f 0 , … , f N − 1 ) \pi= (f_0,\ldots,f_{N-1}) π = ( f 0 , … , f N − 1 ) , where all f i : E X → A f_i : E_X \to A f i : E X → A are measurable.
Similar to the Markov decision model case, for a policy π \pi π and initial state x ∈ E X x \in E_X x ∈ E X , a probability measure P x π \mathbb{P}^{\pi}_x P x π on ( E X × E Y ) N + 1 (E_X \times E_Y)^{N+1} ( E X × E Y ) N + 1 , equipped with the product σ \sigma σ -algebra, is defined as the initial conditional distribution p 0 p_0 p 0 together with transition probability p p p .
For ω = ( x 0 , y 0 , … , x N , y N ) ∈ ( E X × E Y ) N + 1 \omega= (x_0,y_0,\ldots,x_N,y_N) \in(E_X \times E_Y)^{N+1} ω = ( x 0 , y 0 , … , x N , y N ) ∈ ( E X × E Y ) N + 1 , the random variables X n X_n X n and Y n Y_n Y n are defined as
X n ( ω ) = x n and Y n ( ω ) = y n . X_{n}(\omega) = x_{n} \quad\text{and} \quad Y_{n}(\omega) = y_{n}. X n ( ω ) = x n and Y n ( ω ) = y n .
The partially observable Markov decision process is then defined as ( X n , Y n ) n = 0 , … , N (X_{n},Y_{n})_{n=0,\ldots,N} ( X n , Y n ) n = 0 , … , N .
Note that the algorithms shown in § 8.4 only work for Markov decision models. This is because they are based on the Bellman equation and temporal difference learning insights that rely on the Markov property of the environmental dynamics. Nevertheless, the algorithms defined in § 8.4 are used in partially observable Markov decision models (see [14]). In our application, we will apply the TD3 algorithm and check its performance.
Hyperparameter search
This section is based on the paper Algorithms for Hyper-Parameter Optimization [15].
A common problem in training machine learning models is the choice of hyperparameters. For example, when training a deep neural network, the number of hidden layers and the number of nodes within each hidden layer must be carefully chosen, as these parameters determine the complexity of the model and thus lead to possible overfitting or underfitting. Another important hyperparameter that often needs to be tuned is the learning rate. The learning rate determines how much the parameters of the model change after each gradient descent step. If the learning rate is set too low, the model may get stuck in local minima, while if it is set too high, it may keep jumping over the global minima during gradient descent steps. These examples show that the hyperparameters play a crucial role in the training process and the performance of the trained model.
Reinforcement learning algorithms tend to be very sensitive to the choice of parameters used. They also tend to have many hyperparameters. In this section, we show how to automatise the search for good hyperparameters.
In the paper [15], on which this section is based, the authors use tree-structured hyperparameter spaces X \mathcal{X} X . In the sense that some leaf variables (such as the number of nodes in the 2nd layer of a deep neural network) are only well defined if node variables (such as the number of hidden layers of a deep neural network) take certain values.
In our case, we assume that the space of all valid hyperparameters X \mathcal{X} X can be modelled as a bounded subset of ( R m × N n ) (\mathbb{R}^{m} \times\mathbb{N}^{n}) ( R m × N n ) , for some m , n ∈ N m,n \in\mathbb{N} m , n ∈ N .
The problem is to find hyperparameters x ∗ ∈ X x^{*} \in\mathcal{X} x ∗ ∈ X , that minimise a loss
x ∗ ∈ arg min x ∈ X E [ f ( x ) ] , x^{*} \in\underset{x \in\mathcal{X}}{\operatorname{arg\,min}} \mathbb{E}[f(x)], x ∗ ∈ x ∈ X arg min E [ f ( x )] ,
where f ( x ) f(x) f ( x ) is a random variable on ( R , B ( R ) ) (\mathbb{R}, \mathcal{B}(\mathbb{R})) ( R , B ( R )) . Typically, the value f ( x ) f(x) f ( x ) describes a loss on a training set, after training a model with hyperparameters x x x . As the training process of models is typically random, the performance on the test set is also random.
Examples of real-valued hyperparameters are the learning rate or the variance of a noise process. On the other hand, the number of hidden layers and the number of nodes in the first and last layers of a deep neural network can be given as integers. The ideal number of nodes in the k k k -th layer of a deep neural network can be found by predefining a list of possible neural network shapes and letting the algorithm find the best index from the list. Implementing this concept, we do not need to use the tree-hyperparameter space.
In this bounded case, the simplest and most commonly used methods are the grid search and the random search .
For each hyperparameter, the grid search method discretises the set of parameters into a finite set. Then, for each combination of different hyperparameter values the performance of the model is checked (typically on a test set) and the best performing hyperparameters are used. This method is great for finding combinations of hyperparameters that perform well. The problem is that for a good performance the mesh-size of the grid needs to be small, which is computationally expensive. For 10 hyperparameters with each only 5 different values in the grid search, a total of 5 10 = 9765625 5^{10} = 9765625 5 10 = 9765625 independent training and evaluation cycles must be performed.
The other commonly used method is random search . Here, uniformly (or log-uniformly) hyperparameters are sampled from the bounded set of all valid hyperparameters, evaluated and the performing hyperparameters are then used.
In [16 ] , it was shown that random search, typically, finds hyperparameters as good or better than grid search, within a small fraction of the computation time.
Note that it is possible to find good hyperparameters by hand. But this process usually takes a lot of time and when many hyperparameters are used, it is difficult to keep track of which parameters are causing good or bad training performances.
In the following, we formalise the hyperparameter search process, generalise the set of valid hyperparameters and show algorithms that are able to take into account the history of the hyperparameter search, thus minimising the time spent evaluating bad hyperparameters.
Now, we consider two different Sequential Model-Based Global Optimization (SMBO) algorithms. These algorithms approximate a costly to evaluate function f : X → R f : \mathcal{X} \to\mathbb{R} f : X → R . The following algorithm shows the pseudocode of SMBO algorithms:
Algorithm 4: SMBO algorithm
Data: function f : X → R f:\mathcal{X}\to\mathbb{R} f : X → R , Model of function f f f called M 0 M_0 M 0 , number of iterations T ∈ N T\in\mathbb{N} T ∈ N , loss function S \mathcal{S} S
Result: Observation history H = ( ( x i , f ( x i ) ) ) i = 1 T \mathcal{H}=((x_i,f(x_i)))_{i=1}^{T} H = (( x i , f ( x i )) ) i = 1 T
H ← ∅ \mathcal{H}\leftarrow\varnothing H ← ∅ ;
for i = 1 , … , T i=1,\ldots,T i = 1 , … , T do
x i ← arg min x S ( x , M i − 1 ) x_i\leftarrow\operatorname*{arg\,min}_{x}\mathcal{S}(x,M_{i-1}) x i ← arg min x S ( x , M i − 1 ) ;
Evaluate f ( x i ) f(x_i) f ( x i ) ;
H ← H ∪ ( x i , f ( x i ) ) \mathcal{H}\leftarrow\mathcal{H}\cup(x_i,f(x_i)) H ← H ∪ ( x i , f ( x i )) ;
Fit new model M i M_i M i to H \mathcal{H} H ;
end
SMBO algorithms differ in the loss function S \mathcal{S} S used and on how a new model is fitted to the observation history H \mathcal{H} H .
For the hyperparameter-search, the function f : X → R f:\mathcal{X}\to\mathbb{R} f : X → R is random, i.e. there exists a measurable space ( Ω , F ) (\Omega,\mathcal{F}) ( Ω , F ) with f : X × Ω → R f:\mathcal{X}\times\Omega\to\mathbb{R} f : X × Ω → R and f ( x , ⋅ ) f(x,\cdot) f ( x , ⋅ ) is measurable for all x ∈ X x\in\mathcal{X} x ∈ X . To evaluate the function f f f , a model with parameters in X \mathcal{X} X is trained for a fixed amount of time or iterations and then f ( x ) f(x) f ( x ) is given as the performance of the model on a test set. It is important to note that in this section the performance function f f f becomes smaller the better the performance. Instead of maximising some reward, we want to minimise some loss.
The following algorithms will optimise the Expected Improvement (EI) criterion. For a model M M M of f f f , the expected improvement is the expected value of how much f f f negatively exceeds some threshold y ∗ ∈ R y^{*}\in\mathbb{R} y ∗ ∈ R , i.e.
EI y ∗ ( x ) : = ∫ − ∞ ∞ max ( y ∗ − y , 0 ) p M ( y ∣ x ) d y . \operatorname{EI}_{y^{*}}(x):=\int_{-\infty}^{\infty}\max(y^{*}-y,0)p_M(y\mid x)\,\mathrm{d}y. EI y ∗ ( x ) := ∫ − ∞ ∞ max ( y ∗ − y , 0 ) p M ( y ∣ x ) d y .
Gaussian Processes Approach
In this subsection, we first briefly explain Gaussian processes and then show how they can be used for the hyperparameter search. The theoretical explanation of Gaussian processes is based on [17 ] .
We start with the assumption that f f f has the domain R m \mathbb{R}^{m} R m for a m ∈ N m\in\mathbb{N} m ∈ N and f f f is linear, i.e. a w ∈ R m w\in\mathbb{R}^{m} w ∈ R m exists with f ( x ) = x T w f(x)=x^{T}w f ( x ) = x T w . Further, we assume that the observations of f f f , which we denote by y y y , are given by y = f ( x ) + ϵ y=f(x)+\epsilon y = f ( x ) + ϵ , where epsilon is normally distributed with mean 0.
Let D \mathcal{D} D be a set of n n n observations, i.e. D = { ( x i , y i ) ∣ i = 1 , … , n } ⊆ R m × R \mathcal{D}=\{(x_i,y_i)\mid i=1,\ldots,n\}\subseteq\mathbb{R}^{m}\times\mathbb{R} D = {( x i , y i ) ∣ i = 1 , … , n } ⊆ R m × R . We denote the matrix where the i i i -th column equals x i x_i x i as X ∈ R m × n X \in\mathbb{R}^{m \times n} X ∈ R m × n and y : = ( y 1 , … , y n ) y := (y_1,\ldots,y_n) y := ( y 1 , … , y n ) . Then, we can write D = ( X , y ) D = (X,y) D = ( X , y ) .
Now, assume that the noise ϵ \epsilon ϵ depends on the size of D D D , i.e. ϵ ∼ N ( 0 , σ n 2 ) \epsilon\sim\mathcal{N}(0,\sigma_n^2) ϵ ∼ N ( 0 , σ n 2 ) .
The likelihood (probability density) of observing y y y given X X X and w w w is
p ( y ∣ X , w ) = ∏ i = 1 n p ( y i ∣ x i , w ) = ∏ i = 1 n 1 2 π σ n 2 exp ( − ( y i − x i T w ) 2 2 σ n 2 ) = 1 ( 2 π σ n 2 ) n / 2 exp ( − 1 2 σ n 2 ∥ y − X T w ∥ 2 2 ) , \begin{aligned}
p(y \mid X,w) = \prod_{i=1}^{n} p(y_i \mid x_i,w) = \prod_{i=1}^{n} \frac{1}{\sqrt{2\pi\sigma_n^2}} \exp\left(-\frac{(y_i-x_i^T w)^2}{2\sigma_n^2}\right) \\
&= \frac{1}{(2\pi\sigma_n^2)^{n/2}} \exp\left(-\frac{1}{2\sigma_n^2}\lVert y-X^T w\rVert_2^2\right),
\end{aligned} p ( y ∣ X , w ) = i = 1 ∏ n p ( y i ∣ x i , w ) = i = 1 ∏ n 2 π σ n 2 1 exp ( − 2 σ n 2 ( y i − x i T w ) 2 ) = ( 2 π σ n 2 ) n /2 1 exp ( − 2 σ n 2 1 ∥ y − X T w ∥ 2 2 ) ,
which is the probability density of N ( X T w , σ n 2 I ) \mathcal{N}(X^T w,\sigma_n^2 I) N ( X T w , σ n 2 I ) .
Gaussian processes use priors over the space of parameters. We assume that
w ∼ N ( 0 , Σ p ) , w \sim\mathcal{N}(0,\Sigma_p), w ∼ N ( 0 , Σ p ) ,
where Σ p \Sigma_p Σ p is a covariance matrix. By Bayes’ rule
p ( w ∣ y , X ) = p ( y ∣ X , w ) p ( w ) p ( y ∣ X ) , p(w \mid y,X) = \frac{p(y \mid X,w)p(w)}{p(y \mid X)}, p ( w ∣ y , X ) = p ( y ∣ X ) p ( y ∣ X , w ) p ( w ) ,
where p ( y ∣ X ) p(y \mid X) p ( y ∣ X ) is called the marginal likelihood and is given by
p ( y ∣ X ) = ∫ p ( y ∣ X , w ) p ( w ) d w . p(y \mid X) = \int p(y \mid X,w)p(w)\,dw. p ( y ∣ X ) = ∫ p ( y ∣ X , w ) p ( w ) d w .
The marginal likelihood p ( y ∣ X ) p(y \mid X) p ( y ∣ X ) is independent of the parameter w w w . We obtain
p ( w ∣ X , y ) ∝ exp ( − 1 2 σ n 2 ( y − X T w ) T ( y − X T w ) ) exp ( − 1 2 w T Σ p − 1 w ) p(w \mid X,y) \propto\exp\left(-\frac{1}{2\sigma_n^2}(y-X^T w)^T(y-X^T w)\right)\exp\left(-\frac{1}{2}w^T\Sigma_p^{-1}w\right) p ( w ∣ X , y ) ∝ exp ( − 2 σ n 2 1 ( y − X T w ) T ( y − X T w ) ) exp ( − 2 1 w T Σ p − 1 w )
∝ exp ( − 1 2 ( w − w ˉ ) T ( 1 σ n 2 X X T + Σ p − 1 ) ( w − w ˉ ) ) , \propto\exp\left(-\frac{1}{2}(w-\bar{w})^T\left(\frac{1}{\sigma_n^2}XX^T+\Sigma_p^{-1}\right)(w-\bar{w})\right), ∝ exp ( − 2 1 ( w − w ˉ ) T ( σ n 2 1 X X T + Σ p − 1 ) ( w − w ˉ ) ) ,
where w ˉ : = σ n − 2 ( σ n − 2 X X T + Σ p − 1 ) − 1 X y \bar{w} := \sigma_n^{-2}(\sigma_n^{-2}XX^T+\Sigma_p^{-1})^{-1}Xy w ˉ := σ n − 2 ( σ n − 2 X X T + Σ p − 1 ) − 1 X y . With this, we observe that p ( w ∣ X , y ) p(w \mid X,y) p ( w ∣ X , y ) is the probability density of a normal distribution with mean w ˉ \bar{w} w ˉ and covariance matrix A − 1 A^{-1} A − 1 , where A : = σ n − 2 X X T + Σ p − 1 A := \sigma_n^{-2}XX^T+\Sigma_p^{-1} A := σ n − 2 X X T + Σ p − 1 . Note that w ˉ = 1 σ n 2 A − 1 X y \bar{w} = \frac{1}{\sigma_n^2}A^{-1}Xy w ˉ = σ n 2 1 A − 1 X y .
We analyse the predictive distribution for f ∗ ≜ f ( x ∗ ) f_* \triangleq f(x_*) f ∗ ≜ f ( x ∗ ) at x ∗ x_* x ∗ . Using the formula
p ( f ∗ ∣ x ∗ , X , y ) = ∫ p ( f ∗ ∣ x ∗ , w ) p ( w ∣ X , y ) d w , p(f_* \mid x_*,X,y) = \int p(f_* \mid x_*,w)p(w \mid X,y)\,dw, p ( f ∗ ∣ x ∗ , X , y ) = ∫ p ( f ∗ ∣ x ∗ , w ) p ( w ∣ X , y ) d w ,
it is shown that p ( f ∗ ∣ x ∗ , X , y ) p(f_* \mid x_*,X,y) p ( f ∗ ∣ x ∗ , X , y ) is equal to the probability density of N ( 1 σ n 2 x ∗ T A − 1 X y , x ∗ T A − 1 x ∗ ) \mathcal{N}\left(\frac{1}{\sigma_n^2}x_*^T A^{-1}Xy,x_*^T A^{-1}x_*\right) N ( σ n 2 1 x ∗ T A − 1 X y , x ∗ T A − 1 x ∗ ) .
Thus, the observation y y y of f ( x ∗ ) f(x_*) f ( x ∗ ) with the most likelihood equals 1 σ n 2 x ∗ T A − 1 X y \frac{1}{\sigma_n^2}x_*^T A^{-1}Xy σ n 2 1 x ∗ T A − 1 X y . Additionally, with the variance x ∗ T A − 1 x ∗ x_*^T A^{-1}x_* x ∗ T A − 1 x ∗ shows the confidence in this prediction, given the data ( X , y ) (X,y) ( X , y ) .
Using a feature map or kernel (kernel trick), briefly explained in [11], we extend this theory from a linear problem to non-linear problems. For a feature map φ : R m → R M \varphi:\mathbb{R}^m \to\mathbb{R}^M φ : R m → R M , we set the model of f f f to f ( x ) = φ ( x ) T w f(x)=\varphi(x)^T w f ( x ) = φ ( x ) T w . The predictive distribution p ( f ∗ ∣ x ∗ , X , y ) p(f_*|x_*,X,y) p ( f ∗ ∣ x ∗ , X , y ) has the density of the following normal distribution
N ( 1 σ n 2 φ ( x ∗ ) T A − 1 Φ y , φ ( x ∗ ) T A − 1 φ ( x ∗ ) ) (3) \mathcal{N}\left(\frac{1}{\sigma_n^2}\varphi(x_*)^T A^{-1}\Phi y,\varphi(x_*)^T A^{-1}\varphi(x_*)\right) \tag*{(3)} N ( σ n 2 1 φ ( x ∗ ) T A − 1 Φ y , φ ( x ∗ ) T A − 1 φ ( x ∗ ) ) (3)
where Φ = Φ ( X ) \Phi=\Phi(X) Φ = Φ ( X ) and Φ ( X ) \Phi(X) Φ ( X ) is the aggregation of columns φ ( x i ) \varphi(x_i) φ ( x i ) and A : = σ n − 2 Φ Φ T + Σ p − 1 A:=\sigma_n^{-2}\Phi\Phi^T+\Sigma_p^{-1} A := σ n − 2 Φ Φ T + Σ p − 1 .
Example 2.6.1. The following function is a commonly used feature map:
For some n ∈ N n\in\mathbb{N} n ∈ N , one can consider the function φ n : R → R n + 1 \varphi_n:\mathbb{R}\to\mathbb{R}^{n+1} φ n : R → R n + 1 , where
φ n ( x ) = ( 1 , x , x 2 , … , x n ) T \varphi_n(x)=(1,x,x^2,\ldots,x^n)^T φ n ( x ) = ( 1 , x , x 2 , … , x n ) T Given this feature map, we are now able to model the functions f f f as
f ( x ) = φ n ( x ) T w = w 0 + w 1 x + w 2 x 2 + ⋯ + w n x n f(x)=\varphi_n(x)^T w=w_0+w_1x+w_2x^2+\cdots+w_nx^n f ( x ) = φ n ( x ) T w = w 0 + w 1 x + w 2 x 2 + ⋯ + w n x n for a w = ( w 0 , … , w n ) ∈ R n + 1 w=(w_0,\ldots,w_n)\in\mathbb{R}^{n+1} w = ( w 0 , … , w n ) ∈ R n + 1 . So with this feature map at hand, we are able to model polynomial functions.
A Gaussian process is formally defined as:
Definition 2.6.2 (Gaussian process). A Gaussian process is a collection of random variables, such that every finite combination of the random variables has a joint Gaussian distribution.
In this case, we write for the function f f f :
f ( x ) ∼ G P ( m ( x ) , k ( x , x ′ ) ) . f(x) \sim\mathcal{GP}(m(x), k(x, x^{\prime})). f ( x ) ∼ G P ( m ( x ) , k ( x , x ′ )) .
Now, we show how Gaussian processes are used to maximise EI y ∗ \operatorname{EI}_{y^*} EI y ∗ , which is defined as
EI y ∗ ( x ) : = ∫ − ∞ ∞ max ( y ∗ − y , 0 ) p M ( y ∣ x ) d y , \operatorname{EI}_{y^*}(x) := \int_{-\infty}^{\infty} \max(y^* - y, 0)p_M(y \mid x)\,\mathrm{d}y, EI y ∗ ( x ) := ∫ − ∞ ∞ max ( y ∗ − y , 0 ) p M ( y ∣ x ) d y ,
for some threshold y ∗ ∈ R y^* \in\mathbb{R} y ∗ ∈ R and M M M a model of f : X → R f : \mathcal{X} \to\mathbb{R} f : X → R . First, set y ∗ y^* y ∗ to the best (lowest) value in the history H \mathcal{H} H , i.e. y ∗ : = min { f ( x i ) , 1 ≤ i ≤ n } y^* := \min\{f(x_i), 1 \leq i \leq n\} y ∗ := min { f ( x i ) , 1 ≤ i ≤ n } . Let the model p M p_M p M in the function EI y ∗ \operatorname{EI}_{y^*} EI y ∗ be the posterior Gaussian processes after observing H \mathcal{H} H . Then, the expected improvement EI y ∗ \operatorname{EI}_{y^*} EI y ∗ gives us for all x ∈ X x \in\mathcal{X} x ∈ X the expected value over all y y y that satisfy y ≤ y ∗ y \leq y^* y ≤ y ∗ . Since a Gaussian process posterior is used, the EI function captures uncertainty and thus models the difference between explored and under-explored regions. How to chose the next to be observed x i x_i x i can be read in detail in [15]. In short, one uses gradient-free evolutionary algorithms for the optimization.
In case the configuration space X \mathcal{X} X is tree-structured, multiple Gaussian processes over the space X \mathcal{X} X are needed, since in the space X \mathcal{X} X not all variables are always well defined: For example, the number of nodes in the 3rd layer of a 2-layer deep neural network. In this case, individual Gaussian processes are used for these conditional hyperparameters.
Tree-structured Parzen Estimator Approach
The Tree-structured Parzen Estimator Approach (TPE) is another SMBO algorithm that is used in the application of this thesis. It works well for tasks with many hyperparameters and unlike the Gaussian process approach, it does not model p ( y ∣ x ) p(y \mid x) p ( y ∣ x ) directly, but instead models p ( x ∣ y ) p(x \mid y) p ( x ∣ y ) and p ( y ) p(y) p ( y ) and then obtains p ( y ∣ x ) p(y \mid x) p ( y ∣ x ) with Bayes’ rule. In this subsection, we give a brief overview of the approach, for a more detailed explanation see [15].
The algorithm is specifically designed for tree-structured configuration spaces and deals with them in the following way: The generative process of the configuration space (for example first choosing the number of layers then the number of nodes within them) is replaced by distributions of configuration priors with nonparametric densities. In our case, where the hyperparameter space X \mathcal{X} X is given as ( R m × N n ) (\mathbb{R}^{m} \times\mathbb{N}^{n}) ( R m × N n ) , for some m , n ∈ N m, n \in\mathbb{N} m , n ∈ N we define the nonparametric densities directly on the configuration priors.
Reinforcement Learning
The probabilities p ( x ∣ y ) p(x|y) p ( x ∣ y ) for x ∈ X x \in\mathcal{X} x ∈ X and y ∈ R y \in\mathbb{R} y ∈ R are then defined using densities l , g l, g l , g as
p ( x ∣ y ) = { l ( x ) if y < y ∗ g ( x ) if y ≥ y ∗ p(x|y) =
\begin{cases}
l(x) & \text{if } y < y^* \\
g(x) & \text{if } y \ge y^*
\end{cases} p ( x ∣ y ) = { l ( x ) g ( x ) if y < y ∗ if y ≥ y ∗
where l , g l, g l , g are non-parametric densities. After observing { x ( 1 ) , … , x ( k ) } \{x^{(1)}, \ldots, x^{(k)}\} { x ( 1 ) , … , x ( k ) } the density l ( x ) l(x) l ( x ) is the non-parametric density using the observations { x ( i ) } \{x^{(i)}\} { x ( i ) } , such that for the loss f ( x ( i ) ) f(x^{(i)}) f ( x ( i ) ) holds f ( x ( i ) ) < y ∗ f(x^{(i)}) < y^* f ( x ( i ) ) < y ∗ . The density g ( x ) g(x) g ( x ) uses the other observations. Unlike the Gaussian process algorithm, where y ∗ y^* y ∗ is chosen as the smallest loss, the TPE algorithm chooses a y ∗ y^* y ∗ that is some quantile 0 < γ < 1 0 < \gamma< 1 0 < γ < 1 of all observations y i y_i y i , i.e. p ( y < y ∗ ) = γ p(y < y^*) = \gamma p ( y < y ∗ ) = γ , which can be approximated without any model for p ( y ) p(y) p ( y ) . Using such a quantile guarantees that both, l l l and g g g will get observations x ( i ) x^{(i)} x ( i ) .
We address now the question which x x x to choose after observing the history H \mathcal{H} H . Note that for all x ∈ X x \in\mathcal{X} x ∈ X , we have
EI y ∗ ( x ) = ∫ − ∞ y ∗ ( y ∗ − y ) p ( y ∣ x ) d y = ∫ − ∞ y ∗ ( y ∗ − y ) p ( x ∣ y ) p ( y ) p ( x ) d y . \operatorname{EI}_{y^*}(x) = \int_{-\infty}^{y^*}(y^* - y)p(y|x)\,dy = \int_{-\infty}^{y^*}(y^* - y)\frac{p(x|y)p(y)}{p(x)}\,dy. EI y ∗ ( x ) = ∫ − ∞ y ∗ ( y ∗ − y ) p ( y ∣ x ) d y = ∫ − ∞ y ∗ ( y ∗ − y ) p ( x ) p ( x ∣ y ) p ( y ) d y .
With the quantile γ = p ( y < y ∗ ) \gamma= p(y < y^*) γ = p ( y < y ∗ ) , we observe that
p ( x ) = ∫ R p ( x ∣ y ) p ( y ) d y = γ l ( x ) + ( 1 − γ ) g ( x ) . p(x) = \int_{\mathbb{R}} p(x|y)p(y)\,dy = \gamma l(x) + (1 - \gamma)g(x). p ( x ) = ∫ R p ( x ∣ y ) p ( y ) d y = γ l ( x ) + ( 1 − γ ) g ( x ) .
We continue with
∫ − ∞ y ∗ ( y ∗ − y ) p ( x ∣ y ) p ( y ) d y = ∫ − ∞ y ∗ ( y ∗ − y ) l ( x ) p ( y ) d y = l ( x ) ( ∫ − ∞ y ∗ y ∗ p ( y ) d y − ∫ − ∞ y ∗ y p ( y ) d y ) = l ( x ) y ∗ γ − l ( x ) ∫ − ∞ y ∗ y p ( y ) d y . \begin{aligned}
\int_{-\infty}^{y^*}(y^* - y)p(x|y)p(y)\,dy
&= \int_{-\infty}^{y^*}(y^* - y)l(x)p(y)\,dy \\
&= l(x)\left(\int_{-\infty}^{y^*} y^*p(y)\,dy - \int_{-\infty}^{y^*} yp(y)\,dy\right) \\
&= l(x)y^*\gamma- l(x)\int_{-\infty}^{y^*}yp(y)\,dy.
\end{aligned} ∫ − ∞ y ∗ ( y ∗ − y ) p ( x ∣ y ) p ( y ) d y = ∫ − ∞ y ∗ ( y ∗ − y ) l ( x ) p ( y ) d y = l ( x ) ( ∫ − ∞ y ∗ y ∗ p ( y ) d y − ∫ − ∞ y ∗ y p ( y ) d y ) = l ( x ) y ∗ γ − l ( x ) ∫ − ∞ y ∗ y p ( y ) d y .
Combined we achieve
E I y ∗ ( x ) = 1 p ( x ) ∫ − ∞ y ∗ ( y ∗ − y ) p ( x ∣ y ) p ( y ) d y = l ( x ) y ∗ γ − l ( x ) ∫ − ∞ y ∗ y p ( y ) d y γ l ( x ) + ( 1 − γ ) g ( x ) = l ( x ) ( y ∗ γ − ∫ − ∞ y ∗ y p ( y ) d y ) γ l ( x ) + ( 1 − γ ) g ( x ) ∝ l ( x ) γ l ( x ) + ( 1 − γ ) g ( x ) = ( γ + g ( x ) l ( x ) ( 1 − γ ) ) − 1 . \begin{aligned}
\mathrm{EI}_{y^*}(x) &= \frac{1}{p(x)}\int_{-\infty}^{y^*}(y^*-y)p(x\mid y)p(y)\,\mathrm{d}y \\
&= \frac{l(x)y^*\gamma-l(x)\int_{-\infty}^{y^*}yp(y)\,\mathrm{d}y}{\gamma l(x)+(1-\gamma)g(x)} \\
&= \frac{l(x)\left(y^*\gamma-\int_{-\infty}^{y^*}yp(y)\,\mathrm{d}y\right)}{\gamma l(x)+(1-\gamma)g(x)} \\
&\propto\frac{l(x)}{\gamma l(x)+(1-\gamma)g(x)} \\
&= \left(\gamma+\frac{g(x)}{l(x)}(1-\gamma)\right)^{-1}.
\end{aligned} EI y ∗ ( x ) = p ( x ) 1 ∫ − ∞ y ∗ ( y ∗ − y ) p ( x ∣ y ) p ( y ) d y = γ l ( x ) + ( 1 − γ ) g ( x ) l ( x ) y ∗ γ − l ( x ) ∫ − ∞ y ∗ y p ( y ) d y = γ l ( x ) + ( 1 − γ ) g ( x ) l ( x ) ( y ∗ γ − ∫ − ∞ y ∗ y p ( y ) d y ) ∝ γ l ( x ) + ( 1 − γ ) g ( x ) l ( x ) = ( γ + l ( x ) g ( x ) ( 1 − γ ) ) − 1 .
To maximise the expected improvement, we need to find a x ∈ X x \in\mathcal{X} x ∈ X that has high probability under l ( x ) l(x) l ( x ) and low probability under g ( x ) g(x) g ( x ) . In each iteration, a large sample of candidates is drawn from the distribution l l l and then evaluated by g ( x ) / l ( x ) g(x)/l(x) g ( x ) / l ( x ) . The candidate x x x with the lowest g ( x ) / l ( x ) g(x)/l(x) g ( x ) / l ( x ) score is then picked to evaluate f ( x ) f(x) f ( x ) .
Summary
In this chapter, we have seen the foundations of reinforcement learning. After defining a Markov Decision Model/Process and a policy, we were able to describe a Markov Decision Process which depends on a policy π \pi π , by changing the probability measure. Then, we presented the Bellman equation and showed that under the structure assumptions 2.2.5 an optimal policy can be calculated, see algorithm 1. As this algorithm only works great for finite action and state spaces, we introduced the algorithms DDPG and TD3 in § 8.4 . As the performance of the algorithms depends on the chosen hyperparameters, we introduced in § 10.2 the automatisation of the search for good hyperparameters.
Physical Background
This chapter introduces the physics behind the synchrotron light source BESSY II. We start with a brief introduction to the basic functionality of BESSY II. Then, we introduce the functionality of the non-linear kicker.
BESSY II
This section is based on my Bachelor’s thesis [11], where minor changes have been made. It gives an intuitive idea of how BESSY II works.
BESSY II is a synchrotron light source located in Adlershof, Berlin. Inside, electrons are first accelerated in a linear accelerator. They are then accelerated to almost the speed of light in a synchrotron. Such a synchrotron consists of multiple deflection magnets that keep the electrons on a circular path, with linear acceleration sections in between to speed them up.
Once the electrons have reached a certain energy level, they are injected into the storage ring. The aim of this thesis is to optimise this injection. The storage ring consists of more deflection magnets and undulators. Undulators are special magnetic arrangements that force the electrons to follow a a slalom course. In this slalom course, the electrons experience acceleration and thus emit energy in form of electromagnetic radiation, called synchrotron radiation. For further explanation, we refer to a paper by Schwinger [18 ] . This synchrotron radiation is then used in a variety of experiments, for example in materials science.
The following image shows all the parts together:
BESSY II
This image shows both rings. The inner ring is the synchrotron, where the electrons are accelerated and the outer ring is the storage ring. The photo on the right shows some magnets in the synchrotron, while the photo on the left shows a section of the storage ring. Furthermore, inside the outer ring, above the synchrotron, we can see the electron gun, that creates and injects the electrons. The injector pre-accelerates the electrons and then injects them into the synchrotron.
In the following, we take a closer look at the different parts.
Deflection magnets
To force the electrons into the circular track, BESSY II uses deflection magnets. Using the principle of the Lorentz force, these magnets bend the path of the electrons.
The Lorentz force law states that the electromagnetic force F ⃗ L \vec{F}_L F L on a point charge of charge q q q at a given point and time is a function of velocity v ⃗ \vec{v} v and magnetic field strength B ⃗ \vec{B} B as
F ⃗ L = q ( v ⃗ × B ⃗ ) . \vec{F}_L = q(\vec{v} \times\vec{B}). F L = q ( v × B ) .
Visually, the Lorentz force law for an electron can be understood as:
Figure 3.2. Visualisation of the Lorentz force law.
Next, we note that the faster the electrons get, the stronger the magnetic fields have to be. This is achieved by using electromagnets whose magnetic field strength can be controlled by the intensity of the electric current.
Linear acceleration sections
In this subsection, we analyse the linear acceleration sections. These are implemented to accelerate the electrons. This is achieved by applying an alternating voltage to tabular electrodes that are aligned in a straight line. When an electron approaches an electrode, the electrode becomes positive to attract the electron. Ideally, as soon as the electron passes through half of the electrode, the electrode gets negative and repels the electron. With this technique we can accelerate the electron by first pulling it towards the electrode and then pushing it away.
This procedure is visualised in the following 2 figures.
First, we attract the electron with the positive electrode:
BESSY II
Figure 3.3. Visualisation of attraction of an electron.
If the electron were to pass through half of the electrode and we wouldn’t change its electrical charge, we would decelerate the electron, which we don’t want.
That is, why we swap the electrical charges of the electrodes:
Figure 3.4. Visualisation of how the electrode changes its electrical charge and pushes the electron.
Now, the first electrode pushes the electron and the next electrode pulls the electron, accelerating it. Note that there is a gap between the two electrodes, so the electron has space to accelerate.
In practice, there are even more electrodes set up after another, to repeat this procedure and accelerate the electron multiple times.
For this technique it is essential to calculate the exact frequencies at which the electrodes must change their electrical charge, otherwise no acceleration takes place and the electrons might slow down. Further, note that these frequencies need to be adapted to the current speed of the electrons, since in the synchrotron setting the electrons go through the same linear acceleration setting several times.
Non-Linear Kicker
In this section, we look at the physical background behind the non-linear kicker. The figure below shows its structure:
Figure 3.5. Structure of the Non-Linear Kicker, by [2]
In figure 3.5, we can see the schematic structure of the non-linear kicker. At the front of the figure, the oval shape shows the cross-section of the beam-line where the stored and newly injected electrons are located. We focus on the two main components: the 4 kicker coils, which we call wires and the titanium coating on the ceramic surface. First, we see how a magnetic field is created around a single wire. Then, we analyse eddy-currents, a side-effect of the changing magnetic fields around a single wire, on the titanium coating and in the last two subsections we combine both analyses and show how to model the non-linear kicker.
Field around a wire
This subsection is based on the book Electromagnetic fields and energy , by H. A. Haus and J. R. Melcher [19 ] .
Now, we analyse the magnetic fields created around the wires. The special arrangement of the wires, combined with the titanium coating, creates the non-linear magnetic field.
Let I = [ 0 , T ] ⊂ R \mathcal{I} = [0, T] \subset\mathbb{R} I = [ 0 , T ] ⊂ R be a time interval, for a T > 0 T > 0 T > 0 and S S S be the cross-sectional area of the wire.
Ampere’s law shows the relationship between the magnetic field density $\mathbf{H}: \mathbb{R}^{3} \times \mathcal{I} \to
Non-Linear Kicker
R 3 \mathbb{R}^{3} R 3 and current density J : R 3 × I → R 3 \mathbf{J}: \mathbb{R}^{3} \times\mathcal{I} \to\mathbb{R}^{3} J : R 3 × I → R 3 :
∮ C H d s = ∫ S J d a + d d t ∫ S ϵ 0 E d a , (4) \oint_{C} \mathbf{H}\mathrm{d}\mathbf{s} = \int_{S} \mathbf{J}\mathrm{d}\mathbf{a} + \frac{\mathrm{d}}{\mathrm{d}t}\int_{S} \epsilon_{0}\mathbf{E}\mathrm{d}\mathbf{a}, \tag*{(4)} ∮ C H d s = ∫ S J d a + d t d ∫ S ϵ 0 E d a , (4)
where C ⊂ R 3 C \subset\mathbb{R}^{3} C ⊂ R 3 is the contour of a surface S ⊂ R 3 S \subset\mathbb{R}^{3} S ⊂ R 3 , E : R 3 × I → R 3 \mathbf{E}: \mathbb{R}^{3} \times\mathcal{I} \to\mathbb{R}^{3} E : R 3 × I → R 3 is the electric field, ϵ 0 ∈ R \epsilon_{0} \in\mathbb{R} ϵ 0 ∈ R is the vacuum permittivity and we fix any time in I \mathcal{I} I . In the following, we assume that the second term on the right hand side describing the field around a changing electric field E \mathbf{E} E is negligible, following the magnetoquasistatic approximation (MQS).
We model the wires as lines, so let the surface area A A A of S S S go to 0 0 0 and the field density to infinity. We get as current I : I → R I: \mathcal{I} \to\mathbb{R} I : I → R
I = lim J → ∞ A → 0 ∫ S J d a . (5) I = \lim_{\substack{\mathbf{J}\to\infty\\A\to0}} \int_{S} \mathbf{J}\mathrm{d}\mathbf{a}. \tag*{(5)} I = J → ∞ A → 0 lim ∫ S J d a . (5)
Combining equations 3.1 and 3.2 we find that the field around a wire is given by
∮ C H d s = I , (6) \oint_{C} \mathbf{H}\mathrm{d}\mathbf{s} = I, \tag*{(6)} ∮ C H d s = I , (6)
using the MQS approximation. If C C C is a circle with radius r r r , we can reformulate the integral on the left hand side to
I = ∮ C H d s = ∫ 0 2 π H φ r d φ . (7) I = \oint_{C} \mathbf{H}\mathrm{d}\mathbf{s} = \int_{0}^{2\pi} H_{\varphi}r\mathrm{d}\varphi. \tag*{(7)} I = ∮ C H d s = ∫ 0 2 π H φ r d φ . (7)
Since the magnetic field density H φ H_{\varphi} H φ does not depend on the angle φ \varphi φ , we find that
I = ∫ 0 2 π H φ r d φ = H φ 0 2 π r (8) I = \int_{0}^{2\pi} H_{\varphi}r\mathrm{d}\varphi= H_{\varphi_0}2\pi r \tag*{(8)} I = ∫ 0 2 π H φ r d φ = H φ 0 2 π r (8)
for any φ 0 ∈ [ 0 , 2 π ] \varphi_{0} \in[0, 2\pi] φ 0 ∈ [ 0 , 2 π ] .
Using the linear constitutive law, the magnetic flux density B : R 3 × I → R 3 \mathbf{B}: \mathbb{R}^{3} \times\mathcal{I} \to\mathbb{R}^{3} B : R 3 × I → R 3 , can be written as B = μ 0 H \mathbf{B} = \mu_{0}\mathbf{H} B = μ 0 H , with μ 0 ∈ R \mu_{0} \in\mathbb{R} μ 0 ∈ R as magnetic vacuum permeability. This gives us
I = H φ 0 2 π r = 1 μ 0 B φ 0 2 π r , (9) I = H_{\varphi_0}2\pi r = \frac{1}{\mu_0}B_{\varphi_0}2\pi r, \tag*{(9)} I = H φ 0 2 π r = μ 0 1 B φ 0 2 π r , (9)
which is equivalent to
B φ 0 = μ 0 I 2 π r , (10) B_{\varphi_0} = \mu_0\frac{I}{2\pi r}, \tag*{(10)} B φ 0 = μ 0 2 π r I , (10)
for all φ 0 ∈ [ 0 , 2 π ] \varphi_0 \in[0, 2\pi] φ 0 ∈ [ 0 , 2 π ] .
This equation allows us to describe the magnetic flux density around a single wire, which we need later.
Modelling eddy current effects
This subsection is based on the book Electromagnetic fields and energy , by H. A. Haus and J. R. Melcher [19 ] .
In the following, we set S S S as the surface of the titanium coating.
When a surface S S S is exposed to a changing magnetic field, induced for example by a changing line current, the motion of the electrons on the surface creates a new current, called an eddy current, which itself induces a magnetic field.
For the non-linear kicker, the changing magnetic field is caused by the changing wire current.
We note that a magnetic field B \mathbf{B} B induces an electric field E \mathbf{E} E . Their relation is given by
∮ C E d s = d d t ∫ S B d a (11) \oint_C \mathbf{E}\,\mathrm{d}s = \frac{\mathrm{d}}{\mathrm{d}t}\int_S \mathbf{B}\,\mathrm{d}a \tag*{(11)} ∮ C E d s = d t d ∫ S B d a (11)
We now focus on the currents induced in the electrically conductive sheet. According to Ohm’s "law", the current induced in the sheet is given by
J = σ E (12) \mathbf{J} = \sigma\mathbf{E} \tag*{(12)} J = σ E (12)
with the conductance σ = 1 ρ \sigma= \frac{1}{\rho} σ = ρ 1 of the material and ρ \rho ρ equal to its specific resistance.
Using Ampere’s law, see 3.1, we can write the surface current K K K as the fields tangential to the surface, i.e.
− H t a + H t b = K , (13) -H_t^a + H_t^b = K, \tag*{(13)} − H t a + H t b = K , (13)
where H t a H_t^a H t a is the magnetic field density generated by the wire and H t b H_t^b H t b by the eddy current.
Since K K K is the surface current and J J J the current density, we get
K ≡ Δ m J = Δ m σ E , thus E = K Δ m σ , (14) K \equiv\Delta_m J = \Delta_m \sigma E,\ \text{ thus }\ E = \frac{K}{\Delta_m \sigma}, \tag*{(14)} K ≡ Δ m J = Δ m σ E , thus E = Δ m σ K , (14)
where Δ m \Delta_m Δ m is the thickness of the material.
Non-Linear Kicker
Combining equations 3.8 and 3.11 we get
K ∮ C d s Δ m ( s ) σ ( s ) = d d t ∫ S B d a (15) K \oint_C \frac{\mathrm{d}s}{\Delta_m(s)\sigma(s)} = \frac{\mathrm{d}}{\mathrm{d}t}\int_S \mathbf{B}\mathrm{d}a \tag*{(15)} K ∮ C Δ m ( s ) σ ( s ) d s = d t d ∫ S B d a (15)
Since the thickness Δ m ( s ) \Delta_m(s) Δ m ( s ) and the conductivity σ ( s ) \sigma(s) σ ( s ) are uniform we get
K P Δ m σ = d d t ∫ S B d a , (16) \frac{KP}{\Delta_m\sigma} = \frac{\mathrm{d}}{\mathrm{d}t}\int_S \mathbf{B}\mathrm{d}a, \tag*{(16)} Δ m σ K P = d t d ∫ S B d a , (16)
where P ∈ R P \in\mathbb{R} P ∈ R is the peripheral length of C C C .
We assume that the material is perfectly conducting, so σ = ∞ \sigma= \infty σ = ∞ holds, thus the left side of the above equation is 0.
We thus get
0 = d d t ∫ S B d a = ∫ S d d t B d a , (17) 0 = \frac{\mathrm{d}}{\mathrm{d}t}\int_S \mathbf{B}\mathrm{d}a = \int_S \frac{\mathrm{d}}{\mathrm{d}t}\mathbf{B}\mathrm{d}a, \tag*{(17)} 0 = d t d ∫ S B d a = ∫ S d t d B d a , (17)
where the second equation follows the Leibniz integral rule.
Since equation 3.14 holds for any surface S S S , the integrand
d d t B d a = 0. (18) \frac{\mathrm{d}}{\mathrm{d}t}\mathbf{B}\mathrm{d}a = 0. \tag*{(18)} d t d B d a = 0. (18)
Therefore, at the surface boundary any time varying magnetic inductance B B B perpendicular to the surface must be 0.
The line current of a perfectly conducting sheet can be modelled by placing a "mirror line current" opposite to the line current (similar to the construction of the light path of a mirror in geometrical optics).
The resulting magnetic field is then perpendicular to the surface vector.
Then, we calculate the resulting field, which is shown in Figure 3.7 in the following subsection.
Figure 3.7. On the x-axis the position relative to the centre of the cross-section of the storage ring can be seen, on the y-axis the magnetic field measured by the FEM model and the approximation we used for our studies.
The following figure shows the position of all the wires and where the "mirror line currents" have been placed.
Figure 3.6. Position of the wires and "mirror line currents" in the storage ring cross-section.
In the figure 3.6, we can see the positions of the wires and the "mirror line currents" in the cross-section of the storage ring. Note that the titanium coating is both on the top and bottom of the storage ring. The "mirror line currents" have been placed in the positions shown, to model the magnetic field being orthogonal to the titanium surface. In the real non-linear kicker there are no "mirror line currents".
Modelling the Non-Linear Kicker
We model the non-linear kicker field as a 2-dimensional field, since the effects on the beam are modelled as an infinitely thin kick. The kicker consists of 4 wires which are activated by a short pulse. A thin titanium coating is placed on the surface. This arrangement creates a magnetic field, which we model in the following way:
The following figure shows the magnetic field measured by the FEM model and the approximation we used for our studies.
We can see that our model does not fit the FEM calculation perfectly. But for x-values between -15mm and +15mm the approximation is close enough for our further analysis.
Thin Lens Approximation
This subsection should give an intuitive idea of why we can model the non-linear kicker field as an infinitely thin element.
First, note that magnetic fields deflect electric charges q q q by
F L = q v × B , (19) \mathbf{F}_{L}=q\mathbf{v}\times\mathbf{B}, \tag*{(19)} F L = q v × B , (19)
where v \mathbf{v} v is the velocity and the force F L \mathbf{F}_{L} F L is called the Lorentz-force.
Since the electron velocity in BESSY II is highly relativistic, i.e. very close to the speed of light, the electrons "see" the non-linear kicker as a rather short element, in particular due to the relativistic space contraction effect. Therefore, we model the non-linear kicker as an infinitely thin lens, and it only affect the direction of the electrons path. The non-linear kicker changes the electron impulse p p p by
Δ p x = − L ⋅ B y Δ p y = − L ⋅ B x . (20) \Delta p_{x}=-L\cdot B_{y}\qquad\Delta p_{y}=-L\cdot B_{x}. \tag*{(20)} Δ p x = − L ⋅ B y Δ p y = − L ⋅ B x . (20)
Physical Background
Properly, beam dynamics can be treated using Hamiltonian dynamics, see for example [20 ] . These analyses show that one must take into account the effect of the derivative of the magnetic field.
Furthermore, the path of the electrons through a device are modelled by a sequence of "drift-kicks", i.e. a sequence of drifting/flying for a finite length through a device and then adding the effect of the magnetic fields to the direction of flight. For a short device this can be reduced to a single kick and drift cycle.
Round-to-round behaviour
As described at the end of the last section, the path of electrons through a device can be modelled by a sequence of "drift-kicks", see [21 ] . This can also be done for the whole storage ring of BESSY II, which consists of a large number of magnets and drift sections.
The following figure shows the typical behaviour of newly injected electrons in the first few rounds:
Note that in Figure 3.8 , the x x x -axis shows the x x x -dimensional position of the electrons with respect to the centre of the beam line in mm. On the y y y -axis the direction of flight is given in mrad. As we are only kicking in x x x dimension, these values are sufficient to consider.
Figure 3.8. Example of phase space transition at the NLK for storage ring Sirius (in Brazil). Blue first round, red second, green third and yellow fourth round. The beam for next 210 rounds is shown in grey. Original plot from Lin Liu et al. [22 ] . Image was mirrored, so that the injected is placed on the right side. For this storage ring the injection happens at around 6mm, in our case at 15mm
Each dot represents an electron and each coloured cloud consists of 1000 electrons. The grey dots represent the electrons in the next 210 turns. We observe that they follow a phase space transition path.
Since the path of an electron can be calculated from the sequence of "drift-kicks" we assume that there exists a function T : [ − 1 , 1 ] × R 2 → R 2 \mathcal{T} : [-1,1] \times\mathbb{R}^{2} \to\mathbb{R}^{2} T : [ − 1 , 1 ] × R 2 → R 2 , i.e. for all non-linear kicker strengths a ∈ [ − 1 , 1 ] a \in[-1,1] a ∈ [ − 1 , 1 ] and ( x , p x ) ∈ R 2 (x,p_x) \in\mathbb{R}^{2} ( x , p x ) ∈ R 2 values of an electron at an beam monitor close to the septum-sheet, which will be explained below in subsection 3.4.1, the vector
( x ′ , p x ′ ) = T ( a , x , p x ) ∈ R 2 , (x',p_x') = \mathcal{T}(a,x,p_x) \in\mathbb{R}^{2}, ( x ′ , p x ′ ) = T ( a , x , p x ) ∈ R 2 ,
gives us the x-position x ′ x' x ′ and the direction of flight value p x ′ p_x' p x ′ of the electron in the next round at the septum-sheet. For now, we assume that the round-to-round behaviour T \mathcal{T} T is deterministic. In the model description section 4.2 we add noise to this round-to-round behaviour, which can be induced by measurement errors and imperfect magnetic fields.
We also assume that functions
T μ : [ − 1 , 1 ] × R 2 × R 2 , 2 → R 2 and T Σ : [ − 1 , 1 ] × R 2 × R 2 , 2 → R 2 , 2 \mathcal{T}^{\mu} : [-1,1] \times\mathbb{R}^{2} \times\mathbb{R}^{2,2} \to\mathbb{R}^{2}
\quad\text{and}\quad
\mathcal{T}^{\Sigma} : [-1,1] \times\mathbb{R}^{2} \times\mathbb{R}^{2,2} \to\mathbb{R}^{2,2} T μ : [ − 1 , 1 ] × R 2 × R 2 , 2 → R 2 and T Σ : [ − 1 , 1 ] × R 2 × R 2 , 2 → R 2 , 2
exists, which allows the prediction of the distribution of the electrons in the next round, given the kicker strength a a a , the x x x , p x p_x p x mean and covariance of the normally distributed electrons at the septum-sheet.
Intuition
In the last section we have seen how to calculate the round-to-round behaviour using "drift-kicks". In this section we present a first analysis of the injection problem using a simulation of BESSY II, that was made using the "drift-kicks". First, we analyse the number of rounds before the electrons collide with the septum sheet. Second, we investigate how to use the non-linear kicker optimally.
Without Kick
In this subsection, we investigate how many rounds the electrons survive without being kicked by the non-linear kicker.
Note that in BESSY II, there is a barrier in the beam line which causes the loss of electrons. The following figure 3.9 shows a visualisation.
Intuition
The stored beam is located in the centre of the cross section of the beam line, as seen in Figure 3.9 . The barrier shown is a magnet, called the septum-sheet. It plays an important role in the 4-kicker bump, seen in Figure 1.1 , as it merges the injected electrons with the stored electrons. It is also important for the non-linear kicker injection, as it pulls the electrons towards the centre of the beam line. The position of the septum-sheet, in comparison to the non-linear kicker, is shown in Figure 3.1 .
Figure 3.1. Basic setup of BESSY II , provided by the Helmholtz Zentrum Berlin. The inner ring shows a synchrotron, the outer ring is called storage ring. The small straight section above the synchrotron is the electron gun, where electrons are created. At the mark 1, the septum-sheet is located; at mark 2 the non-linear kicker. The role of the septum-sheet is explained in subsection 3.4.1.
Figure 3.9. Visualisation of the cross-section of the beam line and a barrier, called the septum sheet. In the first round, the newly injected electrons are to the right of the septum-sheet. In the next rounds they are located to the left of the septum-sheet. The stored beam is located in the centre of the beam line.
In the first round, where the electrons are injected, the electrons are on the right side of the septum-sheet. In the following rounds, the location of the electrons at the septum-sheet must be on the left side of the septum-sheet. Otherwise, the electrons have crashed into the septum-sheet and are considered lost.
As the electrons follow a phase transition path, visualised in Figure 3.8 , they will eventually crash into the septum-sheet, so we need to influence them with the nonlinear kicker.
To visualise the amount of rounds the electrons survive without the non-linear kicker, we have created a plot, that shows for x x x , p x p_x p x values of single electrons at the septum-sheet how many rounds they survive without any influence from the non-linear kicker.
We further assume that there is no noise in the round-to-round behaviour. The results are given in the following Figure 3.10 .
Figure 3.10. Plot showing the amount of rounds newly injected electrons survive without kick. The area within the orange lines shows the injection area selected for the studies presented here.
Physical Background
On the x x x -axis, we observe the x x x -position of the electrons with respect to the centre of the beam line. Note that these x x x -positions are > 15 m m > 15\mathrm{mm} > 15 mm because the septum-sheet is positioned at 15mm and we focus here on newly injected electrons. On the y y y -axis, we can see the direction of flight of the electrons in mrad. The direction of flight value gives in mrad in which angle the electrons are moving left/right as they fly. The colour in the middle (at x = 19 m m x = 19\mathrm{mm} x = 19 mm , p x = 0.0 m r a d p_x = 0.0\mathrm{mrad} p x = 0.0 mrad ) represents 6 rounds, above this area we have 4 rounds, below a single round and the 3 small areas represent from bottom to top: 7,13 and 15 rounds.
Within this plot we highlighted an area which we call injection area for further studies. It was selected due to boundary conditions of the BESSY II machine. The area is described as the region between 2 polynomial functions. For our injection problem, we assume that the mean values of the electron distribution at the beginning of the injection are within this area.
In particular, the plot 3.10 shows that we do not need to kick the electrons in the very first round. Instead, there are at least five rounds in the injection area that we could wait for before taking action. In the following subsection, we provide an understanding of when and how the electrons are kicked optimally.
Optimal Kicker Usage
In this subsection, we give an introduction to when and how to use the non-linear kicker optimally. For now, we continue our analysis on a deterministic system. First, we state a necessary condition that electrons must fulfil to be successfully kicked and then show how to find the optimal kicker strength.
The necessary condition for a single electron is:
The x x x -position of the electron at the non-linear kick must be between − 15 m m -15\mathrm{mm} − 15 mm and + 15 m m +15\mathrm{mm} + 15 mm .
Suppose an electron does not satisfy this condition. Since the electrons follow a phase space transition, as shown in the Figure 3.8 , no matter much how we change the p x p_x p x value of the electron, after a few rounds it reaches the 15 m m 15\mathrm{mm} 15 mm mark at the non-linear kicker, thus also at the septum-sheet and therefore they crash into it. For this reason, the condition must be fulfilled.
Now assume that at the non-linear kicker the x x x -position of an electron is within ( − 15 m m , 15 m m ) (-15\mathrm{mm},15\mathrm{mm}) ( − 15 mm , 15 mm ) . If we could now use the non-linear kicker to change the direction of flight value p x p_x p x of the electron to approximately 0 0 0 , the electron survives the injection. As in the phase space transition a p x p_x p x value of 0 0 0 indicates that the electron is at the highest/lowest x x x -value it will get. For this reason, all further x x x -values of the electron at the non-linear kicker, including the septum sheet will not exceed the value 15 m m 15\mathrm{mm} 15 mm and therefore will not crash into the septum-sheet.
Now, we show how the linearity of the magnetic field strength with respect to the kicker strength is used to calculate the optimal kicker strength. Let ( x , p x ) (x,p_x) ( x , p x ) be the information of an electron at the non-linear kicker. Assume that x ∈ ( − 15 m m , 15 m m ) x \in(-15\mathrm{mm},15\mathrm{mm}) x ∈ ( − 15 mm , 15 mm ) . Let B ( α , x ) \mathcal{B}(\alpha,x) B ( α , x ) be the function that maps the kicker strength α ∈ [ − 1 , 1 ] \alpha\in[-1,1] α ∈ [ − 1 , 1 ] and x x x position of an electron to the change in p x p_x p x value, i.e. p x ′ = p x + B ( α , x ) p'_x = p_x + \mathcal{B}(\alpha,x) p x ′ = p x + B ( α , x ) , where p x ′ p'_x p x ′ is the p x p_x p x value of the electron immediately after the non-linear kicker. Note that B \mathcal{B} B is linear in α \alpha α . The optimal kicker strength α ∗ \alpha^* α ∗ is calculated as
p x ′ ! = 0 = p x + B ( α ∗ , x ) ⇔ α ∗ B ( 1 , x ) = − p x ⇔ α ∗ = − p x B ( 1 , x ) . p'_x \mathrel{!}= 0 = p_x + \mathcal{B}(\alpha^*,x) \quad\Leftrightarrow\quad\alpha^*\mathcal{B}(1,x) = -p_x \quad\Leftrightarrow\quad\alpha^* = -\frac{p_x}{\mathcal{B}(1,x)}. p x ′ ! = 0 = p x + B ( α ∗ , x ) ⇔ α ∗ B ( 1 , x ) = − p x ⇔ α ∗ = − B ( 1 , x ) p x .
With this equation, we have found an easy way to calculate the optimal kicker strength α ∗ \alpha^* α ∗ . Note that for small values of B ( 1 , x ) \mathcal{B}(1,x) B ( 1 , x ) or large values of p x p_x p x , the calculated strength α ∗ \alpha^* α ∗ may not be realisable, as it is no longer within [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . In this case, it is not possible to kick the electrons optimally.
The following plots show the x , p x x,p_x x , p x values at the septum-sheet in the very first round,
Physical Background
when the values meet the condition (not the white regions) and when the kick was successful (yellow (1000) region). In all other regions (not white or yellow), the kick was not successful. There are several reasons for this, but the most common one is that the simulation has difficulties with some borderline cases.
Figure 3.11. Regions where electrons can be optimally kicked in round 0
Figure 3.12. Regions where electrons can be optimally kicked in round 1
Intuition
Figure 3.13. Regions where electrons can be optimally kicked in round 2
Figure 3.14. Regions where electrons can be optimally kicked in round 3
Figure 3.15. Regions where electrons can be optimally kicked in round 8
Physical Background
These figures show for which initial values the electrons are successfully kicked, depending on which round the non-linear kicker was activated. We observe that it is not optimal to kick only in round 0 or in any other round, as different rounds cover different regions. Interestingly, using the non-linear kicker in round 1 is significantly worse compared to the rounds 0,2,3. The plots for all other rounds can be seen in the programming reference, referenced at the beginning of the chapter 5.
The next plots show the area in which electrons are successfully kicked, together with the optimal kicker strength for the whole beam line. The x x x and p x p_x p x values shown are measured at the septum-sheet. All regions in Figure 3.16 , with values between 0 and 1000, meet the necessary condition for a successful kick. For the yellow area (value: 1000) the kick is successful. The values -200 in Figure 3.16 and -1 in Figure 3.17 are just background colours to highlight the other regions.
Figure 3.16. Given x,px values at the septum sheet, the plot shows for which of them the injection can be done (score: 1000 rounds).
Figure 3.17. Corresponding optimal kicker strength, see figure 3.16.
Intuition
We intend to answer the question of how the injection efficiency changes for different kicker strengths. For this experiment, we added noise to the round-to-round behaviour, that is for both x x x and p x p_x p x we added zero mean normal distributed noise, where the noise for the x x x values had std: 6.5 ⋅ 10 − 6 m 6.5 \cdot10^{-6}\,\mathrm{m} 6.5 ⋅ 1 0 − 6 m and for p x p_x p x std: 5.2 ⋅ 10 − 6 m 5.2 \cdot10^{-6}\,\mathrm{m} 5.2 ⋅ 1 0 − 6 m . For an explanation of why we chose these noise values see subsection 5.1.1. No specific noise was added to the kicker strength. The following figure shows the result
In Figure 3.18 , we observe that the injection efficiency is highest around the optimal kicker strength with a small plateau. Outside the plateau we see a very steep drop in efficiency.
Figure 3.18. For each kicker strength, we run 1000 simulations with the same parameters (x-value 16.4mm, px 0.0mm, activated NLK in round 4 with given kicker strength). The y-value shows in how many of these 1000 experiments the electron survived. The green dashed line shows the optimal kicker strength.
Effect on stored beam
The following figure shows the absolute effect in the direction of flight (in mrad) for different x / p x x/p_x x / p x values at the septum sheet close to the centre, where the stored beam is.
In the figure Figure 3.19 we observe the effect of the non-linear kicker, activated with the highest possible strength 1, on the stored electrons which lie in the range of -1mm to 1mm. We observe that the change in direction of flight is in the range of [ − 0.04 m r a d , 0.04 m r a d ] [-0.04\mathrm{mrad}, 0.04\mathrm{mrad}] [ − 0.04 mrad , 0.04 mrad ] , which is not significantly higher than the previous values. As the non-linear kicker is typically not used at full strength, the effect is even less, see Figure 3.17 .
Figure 3.19. Plot showing the difference in direction of flight, created by the non-linear kicker with strength 1. Each x / p x x/p_x x / p x value shows the value at the septum sheet.
Problem Modelling
In this chapter, we examine how to model the non-linear kicker injection as a Markov Decision Process.
Problem Description
In this section, we describe exactly what the non-linear kicker injection problem is.
The goal of the injection problem is to maximise the number of electrons that survive the injection. We say that an electron has survived the injection if it does not crash into the septum-sheet in the first 1000 rounds.
To achieve this goal, the use of the non-linear kicker must be optimised. The activation round of the kicker and the kicker-strength are to choose. Underlying, there is the constraint that the non-linear kicker can only be activated once, as we do not have enough time during the injection to recharge the non-linear kicker.
At the beginning of the injection process the electrons have a normal distributed shape. They maintain this normal distributed shape in each round, unless some of the electrons crash into the septum-sheet. In this case, the electrons follow a truncated normal distribution.
In the next section, we describe this problem as a Markov Decision Process. We propose four descriptions.
In the first 3 descriptions we consider Markov Decision Models with a planning horizon of N = 1000 N = 1000 N = 1000 and assume that we are able to adjust the non-linear kicker as we observe the electrons at the septum-sheet. Although this assumption is unrealistic as the electrons travel at almost the speed of light and the septum-sheet and non-linear kicker are positioned close to each other, we want to analyse how reinforcement learning algorithms deal with such environments. The first environment shows the model environment for truncated normal distributions. In the second, we model the injection for a single electron and then, in the third model, for 1000 electrons.
The last description is the most realistic to implement. In this fourth model, we require that the activation round of the non-linear kicker together with the kicker strength be predicted after the electrons are observed at the septum sheet in the very first round. For details of how this model is implemented at BESSY II see remark 4.2.5.
Model
Definition 4.2.1 (truncated normal distributions). Let μ ∈ R 2 \mu\in\mathbb{R}^{2} μ ∈ R 2 be the mean vector and Σ ∈ R 2 , 2 \Sigma\in\mathbb{R}^{2,2} Σ ∈ R 2 , 2 be the covariance matrix of a 2-dimensional normal distribution with density function
f ( x ; μ , Σ ) ) = 1 ( 2 π ) 2 det ( Σ ) exp ( − 1 2 ( x − μ ) T Σ − 1 ( x − μ ) ) . f(x;\mu,\Sigma)) = \frac{1}{\sqrt{(2\pi)^2\det(\Sigma)}}\exp\left(-\frac{1}{2}(x-\mu)^{T}\Sigma^{-1}(x-\mu)\right). f ( x ; μ , Σ )) = ( 2 π ) 2 det ( Σ ) 1 exp ( − 2 1 ( x − μ ) T Σ − 1 ( x − μ ) ) . We truncate this normal distribution by dividing the R 2 \mathbb{R}^{2} R 2 space into 2 half spaces and setting the density on one half space to zero. To do this, we need a vector y ∈ R 2 y \in\mathbb{R}^{2} y ∈ R 2 and direction z ∈ R 2 z \in\mathbb{R}^{2} z ∈ R 2 . Further, we truncate the density function f f f by:
f 1 ( x ; μ , Σ , y , z ) = { f ( x ; μ , Σ , y , z ) , if ⟨ x − y , z ⟩ > 0 0 , else f^{1}(x;\mu,\Sigma,y,z) =
\begin{cases}
f(x;\mu,\Sigma,y,z), & \text{if } \langle x-y,z\rangle> 0 \\
0, & \text{else}
\end{cases} f 1 ( x ; μ , Σ , y , z ) = { f ( x ; μ , Σ , y , z ) , 0 , if ⟨ x − y , z ⟩ > 0 else where ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ is the standard scalar product on R 2 \mathbb{R}^{2} R 2 . Note that the truncated function f 1 f^{1} f 1 is no longer a density function, since the integral over R 2 \mathbb{R}^{2} R 2 is not 1. We intentionally do not normalise it, to calculate in a straightforward manner how much of the initial distribution remains after the truncation, by taking the integral over the remaining density. In the following, we consider n n n times truncated normal distributions, where for the sequences of vectors ( y k ) k = 1 m : = ( y k ) k = 1 , … , m , ( z k ) k = 1 m : = ( z k ) k = 1 , … , m ⊂ R 2 (y_k)_{k=1}^{m} := (y_k)_{k=1,\ldots,m}, (z_k)_{k=1}^{m} := (z_k)_{k=1,\ldots,m} \subset\mathbb{R}^{2} ( y k ) k = 1 m := ( y k ) k = 1 , … , m , ( z k ) k = 1 m := ( z k ) k = 1 , … , m ⊂ R 2 and all m = 1 , … , n m=1,\ldots,n m = 1 , … , n , we have
f m ( x ; μ , Σ , ( y k ) k = 1 m , ( z k ) k = 1 m ) = { f m − 1 ( x ; μ , Σ , ( y k ) k = 1 m − 1 , ( z k ) k = 1 m − 1 ) , if ⟨ x − y m , z m ⟩ > 0 0 , else f^{m}\left(x;\mu,\Sigma,(y_k)_{k=1}^{m},(z_k)_{k=1}^{m}\right) =
\begin{cases}
f^{m-1}\left(x;\mu,\Sigma,(y_k)_{k=1}^{m-1},(z_k)_{k=1}^{m-1}\right), & \text{if } \langle x-y_m,z_m\rangle> 0 \\
0, & \text{else}
\end{cases} f m ( x ; μ , Σ , ( y k ) k = 1 m , ( z k ) k = 1 m ) = { f m − 1 ( x ; μ , Σ , ( y k ) k = 1 m − 1 , ( z k ) k = 1 m − 1 ) , 0 , if ⟨ x − y m , z m ⟩ > 0 else with f 0 = f f^{0}=f f 0 = f .
Model
Now, we provide the definition of the Markov Decision Model, which shows how the non-linear kicker can be used. After the definition, the details are explained in remark 4.2.2.
We consider the Markov Decision Model with planning horizon N = 1000 N = 1000 N = 1000 with
E : = ⋃ m = 0 999 { ( R 2 × R 2 , 2 × { 0 , 1 } ) m + 1 × { † , † , † } 999 − m } , E := \bigcup_{m=0}^{999} \left\{(\mathbb{R}^{2} \times\mathbb{R}^{2,2} \times\{0,1\})^{m+1} \times\{\dagger,\dagger,\dagger\}^{999-m}\right\}, E := m = 0 ⋃ 999 { ( R 2 × R 2 , 2 × { 0 , 1 } ) m + 1 × { † , † , † } 999 − m } ,
where each element ( ( μ 0 , Σ 0 , k 0 ) , … , ( μ m , Σ m , k m ) , { † , † , † } 999 − m ) ∈ E ((\mu_0,\Sigma_0,k_0),\ldots,(\mu_m,\Sigma_m,k_m),\{\dagger,\dagger,\dagger\}^{999-m}) \in E (( μ 0 , Σ 0 , k 0 ) , … , ( μ m , Σ m , k m ) , { † , † , † } 999 − m ) ∈ E consists of mean vector μ t \mu_t μ t , covariance matrix Σ t \Sigma_t Σ t , the information if the kicker has already been used k t k_t k t for all rounds t = 0 , … , m t = 0,\ldots,m t = 0 , … , m . For the remaining rounds, to indicate that there is no information yet, we denote them with † \dagger † . Further, we equip the state space E E E with the Borel σ \sigma σ -algebra, i.e. E : = B ( E ) \mathcal{E} := \mathcal{B}(E) E := B ( E ) .
Action space A : = [ − 1 , 1 ] A := [-1,1] A := [ − 1 , 1 ] with Borel σ \sigma σ -algebra A : = B ( [ − 1 , 1 ] ) \mathcal{A} := \mathcal{B}([-1,1]) A := B ([ − 1 , 1 ])
To define the stochastic transition kernel p p p , consider the following transitions between time steps. Let T μ , T Σ T^\mu, T^\Sigma T μ , T Σ be the round-to-round transition functions defined in section 3.3. For state s t = ( ( μ 0 , Σ 0 , k 0 ) , … , ( μ t , Σ t , k t ) , { † , † , † } 999 − t ) ∈ E s_t = ((\mu_0,\Sigma_0,k_0),\ldots,(\mu_t,\Sigma_t,k_t),\{\dagger,\dagger,\dagger\}^{999-t}) \in E s t = (( μ 0 , Σ 0 , k 0 ) , … , ( μ t , Σ t , k t ) , { † , † , † } 999 − t ) ∈ E , for a t ∈ { 0 , … , 999 } t \in\{0,\ldots,999\} t ∈ { 0 , … , 999 } and action a t ∈ A a_t \in A a t ∈ A the state at time step t + 1 t+1 t + 1 follows the rules:
a ~ t = ( a t + ε t a ) 1 { a t ≠ 0 } \tilde{a}_t = (a_t + \varepsilon_t^a)\mathbf{1}_{\{a_t\ne0\}} a ~ t = ( a t + ε t a ) 1 { a t = 0 }
μ t + 1 = T μ ( a ~ t ( 1 − k t ) , μ t , Σ t ) + ε t μ \mu_{t+1} = T^\mu(\tilde{a}_t(1-k_t),\mu_t,\Sigma_t) + \varepsilon_t^\mu μ t + 1 = T μ ( a ~ t ( 1 − k t ) , μ t , Σ t ) + ε t μ
Σ t + 1 = T Σ ( a ~ t ( 1 − k t ) , μ t , Σ t ) + ε t Σ \Sigma_{t+1} = T^\Sigma(\tilde{a}_t(1-k_t),\mu_t,\Sigma_t) + \varepsilon_t^\Sigma Σ t + 1 = T Σ ( a ~ t ( 1 − k t ) , μ t , Σ t ) + ε t Σ
k t + 1 = max { k t , 1 { a t ≠ 0 } } k_{t+1} = \max\{k_t,\mathbf{1}_{\{a_t\ne0\}}\} k t + 1 = max { k t , 1 { a t = 0 } }
where ε t a , ε t μ \varepsilon_t^a,\varepsilon_t^\mu ε t a , ε t μ and ε t Σ \varepsilon_t^\Sigma ε t Σ are normal distributed independent noise in R \mathbb{R} R , R 2 \mathbb{R}^2 R 2 and R 2 , 2 \mathbb{R}^{2,2} R 2 , 2 respectively. We then set the state s t + 1 s_{t+1} s t + 1 equal to
s t + 1 = ( ( μ 1 , Σ 1 , k 1 ) , … , ( μ t , Σ t , k t ) , ( μ t + 1 , Σ t + 1 , k t + 1 ) , { † , † , † } 999 − t − 1 ) ∈ E s_{t+1} = ((\mu_1,\Sigma_1,k_1),\ldots,(\mu_t,\Sigma_t,k_t),(\mu_{t+1},\Sigma_{t+1},k_{t+1}),\{\dagger,\dagger,\dagger\}^{999-t-1}) \in E s t + 1 = (( μ 1 , Σ 1 , k 1 ) , … , ( μ t , Σ t , k t ) , ( μ t + 1 , Σ t + 1 , k t + 1 ) , { † , † , † } 999 − t − 1 ) ∈ E
We consider the process ( s t ) t = 0 , … , 100 (s_t)_{t=0,\ldots,100} ( s t ) t = 0 , … , 100 as stochastic process on the measurable space ( E , B ( E ) ) (E,\mathcal{B}(E)) ( E , B ( E )) .
The stochastic transition kernel is set as the natural kernel given the transition rules.
s 0 = ( ( μ 0 , Σ 0 , 0 ) , { † , † , † } 999 ) , s_0 = ((\mu_0,\Sigma_0,0),\{\dagger,\dagger,\dagger\}^{999}), s 0 = (( μ 0 , Σ 0 , 0 ) , { † , † , † } 999 ) ,
Problem Modelling
where μ 0 \mu_0 μ 0 , Σ 0 \Sigma_0 Σ 0 are uniformly distributed from an area, defined in § 20.1.1 .
the running reward function is set to 0, so r : ( x , a ) ↦ 0 r:(x,a)\mapsto0 r : ( x , a ) ↦ 0
discount factor is set to β = 1 \beta=1 β = 1
terminal reward function g : E → R g:E\to\mathbb{R} g : E → R is defined as
g ( s ) = ∫ R 2 ( T g ( s ) ) ( x ) d x g(s)=\int_{\mathbb{R}^2}\left(\mathcal{T}^{g(s)}\right)(x)\mathrm{d}x g ( s ) = ∫ R 2 ( T g ( s ) ) ( x ) d x
where T g ( s ) \mathcal{T}^{g(s)} T g ( s ) is a 1001-times truncated density of a normal distribution. The function T g ( s ) \mathcal{T}^{g(s)} T g ( s ) is defined in the following remark 4.2.2.
Model
Let s t = ( ( μ 0 , Σ 0 , k 0 ) , … , ( μ t , Σ t , k t ) , { † , † , † } 999 − t ) ∈ E s_t = ((\mu_0, \Sigma_0, k_0), \ldots, (\mu_t, \Sigma_t, k_t), \{\dagger, \dagger, \dagger\}^{999-t}) \in E s t = (( μ 0 , Σ 0 , k 0 ) , … , ( μ t , Σ t , k t ) , { † , † , † } 999 − t ) ∈ E be arbitrary. We iteratively define the t + 1 t+1 t + 1 times truncated density of a normal distribution T ( s t ) : R 2 → R \mathcal{T}(s_t): \mathbb{R}^2 \to\mathbb{R} T ( s t ) : R 2 → R .
In definition 4.2.1, we denoted the density of a normal distribution with mean μ \mu μ and covariance matrix Σ \Sigma Σ by f ( x ; μ , Σ ) f(x; \mu, \Sigma) f ( x ; μ , Σ ) and the truncation was given by
f 1 ( x ; μ , Σ , y , z ) = { f ( x ; μ , Σ , y , z ) , if ⟨ x − y , z ⟩ > 0 , 0 , else f^1(x; \mu, \Sigma, y, z) =
\begin{cases}
f(x; \mu, \Sigma, y, z), & \text{if } \langle x-y,z\rangle> 0,\\
0, & \text{else}
\end{cases} f 1 ( x ; μ , Σ , y , z ) = { f ( x ; μ , Σ , y , z ) , 0 , if ⟨ x − y , z ⟩ > 0 , else
In the first round, the truncation is given as f 1 ( x ; μ 0 , Σ 0 , ( 15 , 0 ) , ( 1 , 0 ) ) f^1(x; \mu_0, \Sigma_0, (15,0), (1,0)) f 1 ( x ; μ 0 , Σ 0 , ( 15 , 0 ) , ( 1 , 0 )) . We use y 1 = ( 15 , 0 ) ∈ R 2 y_1 = (15,0) \in\mathbb{R}^2 y 1 = ( 15 , 0 ) ∈ R 2 , because the septum-sheet is at the x-value 15mm and z 1 = ( 1 , 0 ) z_1 = (1,0) z 1 = ( 1 , 0 ) , as the electrons with x-value lower or equal the value of 15mm are truncated, since in the first round the electrons are outside (to the right) of the septum-sheet.
To propagate truncations from one round to the next, we assume that functions
y ′ = T y ( μ t , Σ t , μ t + 1 , Σ t + 1 , y ) and z ′ = T z ( μ t , Σ t , μ t + 1 , Σ t + 1 , z ) y' = \mathcal{T}^{y}(\mu_t, \Sigma_t, \mu_{t+1}, \Sigma_{t+1}, y) \quad\text{and} \quad z' = \mathcal{T}^{z}(\mu_t, \Sigma_t, \mu_{t+1}, \Sigma_{t+1}, z) y ′ = T y ( μ t , Σ t , μ t + 1 , Σ t + 1 , y ) and z ′ = T z ( μ t , Σ t , μ t + 1 , Σ t + 1 , z )
exist, that are able to propagate the truncations. This can be achieved by using the round-to-round behaviour function for single electrons T \mathcal{T} T , where one could follow the edge of the truncation. Note that for the function T y \mathcal{T}^{y} T y and T z \mathcal{T}^{z} T z , the information of the mean and covariance at time-points t t t and t + 1 t+1 t + 1 are needed, in order to take the noise into account. For well-posedness, we set μ 1002 : = T μ ( 0 , μ 1001 ) \mu_{1002} := \mathcal{T}^{\mu}(0,\mu_{1001}) μ 1002 := T μ ( 0 , μ 1001 ) , analogous for Σ 1002 \Sigma_{1002} Σ 1002 . We do not go into more detail, as these functions are not needed in our implementation.
Instead, we continue to iteratively define the function T \mathcal{T} T . Suppose we have already truncated the normal distribution m m m -times with vectors ( y k ) k = 1 m , ( z k ) k = 1 m (y_k)_{k=1}^{m}, (z_k)_{k=1}^{m} ( y k ) k = 1 m , ( z k ) k = 1 m . Now we propagate them to the next round with
y k ′ : = T y ( μ t , Σ t , μ t + 1 , Σ t + 1 , y k ) and z k ′ : = T z ( μ t , Σ t , μ t + 1 , Σ t + 1 , z k ) . (21) y'_k := \mathcal{T}^{y}(\mu_t, \Sigma_t, \mu_{t+1}, \Sigma_{t+1}, y_k) \quad\text{and} \quad z'_k := \mathcal{T}^{z}(\mu_t, \Sigma_t, \mu_{t+1}, \Sigma_{t+1}, z_k). \tag*{(21)} y k ′ := T y ( μ t , Σ t , μ t + 1 , Σ t + 1 , y k ) and z k ′ := T z ( μ t , Σ t , μ t + 1 , Σ t + 1 , z k ) . (21)
Additionally, we add the truncation from the new round and set
( y 1 ′ , … , y m ′ , ( 15 , 0 ) ) and ( z 1 ′ , … , z m ′ , ( − 1 , 0 ) ) (y'_1,\ldots,y'_m,(15,0)) \quad\text{and} \quad(z'_1,\ldots,z'_m,(-1,0)) ( y 1 ′ , … , y m ′ , ( 15 , 0 )) and ( z 1 ′ , … , z m ′ , ( − 1 , 0 ))
as the truncations for the next round. Note that the new z-value is set to ( − 1 , 0 ) (-1,0) ( − 1 , 0 ) , as now all electrons with an x-value greater or equal 15mm are truncated.
We continue with these truncations up to round t t t . Let ( y k ) k = 1 t , ( z k ) k = 1 t (y_k)_{k=1}^{t}, (z_k)_{k=1}^{t} ( y k ) k = 1 t , ( z k ) k = 1 t be the final truncations. We then define the function T g ( s t ) \mathcal{T}^{g}(s_t) T g ( s t ) as
T g ( s t ) : = f t ( ⋅ ; μ t , Σ t , ( y k ) k = 1 t , ( z k ) k = 1 t ) . \mathcal{T}^{g}(s_t) := f^t(\cdot; \mu_t, \Sigma_t, (y_k)_{k=1}^{t}, (z_k)_{k=1}^{t}). T g ( s t ) := f t ( ⋅ ; μ t , Σ t , ( y k ) k = 1 t , ( z k ) k = 1 t ) .
Now, we use use this function to determine the percentage of electrons that survived the 1000 rounds by calculating
g ( s t ) = ∫ R 2 ( T g ( s t ) ) ( x ) d x . g(s_t) = \int_{\mathbb{R}^{2}} \left(\mathcal{T}^{g}(s_t)\right)(x)\mathrm{d}x. g ( s t ) = ∫ R 2 ( T g ( s t ) ) ( x ) d x .
Note that T g \mathcal{T}^{g} T g is integrable because only finite truncations have been made. Also, the function g g g is measurable since T g ( s t ) \mathcal{T}^{g}(s_t) T g ( s t ) is measurable.
This ends the part on the Markov Decision Process (MDP). The explained MDP models the problem of deciding when to activate the non-linear kicker and with what strength, under the unrealistic assumption that we have enough time to process the information and activate the non-linear kicker. The problem with this modelling is the high dimensional state space and the computational cost of dealing with distributions. Instead, we introduce slightly modified MDPs and Partially Observable Markov Decision Processes (POMDPs), which describe the problem of optimally using the non-linear kicker in different scenarios and levels of difficulty. In the first model, we have limited ourselves to a single electron. After that we see a POMDP for 1000 electrons and at the end a one-step POMDP for 1000 electrons.
Single Electron Kick
For the single electron kick, we consider the following Markov Decision Model with planning horizon N = 1000 N = 1000 N = 1000 with
E : = R 2 × { 0 , 1 } × { 0 , … , 1000 } × { 0 , 1 } E := \mathbb{R}^{2} \times\{0,1\} \times\{0,\ldots,1000\} \times\{0,1\} E := R 2 × { 0 , 1 } × { 0 , … , 1000 } × { 0 , 1 }
where each element ( x , p x , k , r , i ) ∈ E (x,p^{x},k,r,i) \in E ( x , p x , k , r , i ) ∈ E consists of the current x-position x x x and the direction of flight information p x p^{x} p x , if the kicker has already been activated k k k , the round number r ∈ { 0 , … , 1000 } r \in\{0,\ldots,1000\} r ∈ { 0 , … , 1000 } and the information i i i whether the electron has hit the septum-sheet or not. Furthermore, we equip the state space E E E with the Borel σ \sigma σ -algebra, i.e. E : = B ( E ) \mathcal{E} := \mathcal{B}(E) E := B ( E ) .
Action space A : = [ − 1 , 1 ] \mathcal{A} := [-1,1] A := [ − 1 , 1 ] with Borel σ \sigma σ -algebra A : = B ( [ − 1 , 1 ] ) \mathcal{A} := \mathcal{B}([-1,1]) A := B ([ − 1 , 1 ])
between time steps. Let T T T be the round-to-round transition function defined in § 13.1 . For state s t = ( x t , p t x , k t , r t , i t ) s_t=(x_t,p_t^x,k_t,r_t,i_t) s t = ( x t , p t x , k t , r t , i t ) , for a t ∈ { 0 , … , 999 } t\in\{0,\ldots,999\} t ∈ { 0 , … , 999 } and action a t ∈ A a_t\in A a t ∈ A , the state at time step t + 1 t+1 t + 1 follows the rules:
a ~ t = ( a t + ε t a ) 1 { a t ≠ 0 } ( x t + 1 , p t + 1 x ) = T ( a ~ t ( 1 − k t ) , x t , p t x ) + ( ε t x , ε t p x ) k t + 1 = max { k t , 1 { a t ≠ 0 } } r t + 1 = r t + 1 i t + 1 = max { i t , 1 { x t + 1 ≥ 15 m m } } \begin{aligned}
\tilde{a}_t &= (a_t+\varepsilon_t^a)\mathbf{1}_{\{a_t\ne0\}} \\
(x_{t+1},p_{t+1}^x) &= T\left(\tilde{a}_t(1-k_t),x_t,p_t^x\right)+(\varepsilon_t^x,\varepsilon_t^{p^x}) \\
k_{t+1} &= \max\{k_t,\mathbf{1}_{\{a_t\ne0\}}\} \\
r_{t+1} &= r_t+1 \\
i_{t+1} &= \max\{i_t,\mathbf{1}_{\{x_{t+1}\ge15\mathrm{mm}\}}\}
\end{aligned} a ~ t ( x t + 1 , p t + 1 x ) k t + 1 r t + 1 i t + 1 = ( a t + ε t a ) 1 { a t = 0 } = T ( a ~ t ( 1 − k t ) , x t , p t x ) + ( ε t x , ε t p x ) = max { k t , 1 { a t = 0 } } = r t + 1 = max { i t , 1 { x t + 1 ≥ 15 mm } }
where ε t a , ε t x \varepsilon_t^a,\varepsilon_t^x ε t a , ε t x and ε t p x \varepsilon_t^{p^x} ε t p x are normal distributed independent noise in R \mathbb{R} R . We then set the state s t + 1 s_{t+1} s t + 1 equal to
s t + 1 = ( x t + 1 , p t + 1 x , k t + 1 , r t + 1 , i t + 1 ) ∈ E s_{t+1}=(x_{t+1},p_{t+1}^x,k_{t+1},r_{t+1},i_{t+1})\in E s t + 1 = ( x t + 1 , p t + 1 x , k t + 1 , r t + 1 , i t + 1 ) ∈ E
We consider the process ( s t ) t = 0 , … , 1000 (s_t)_{t=0,\ldots,1000} ( s t ) t = 0 , … , 1000 as a stochastic process on the measurable space ( E , B ( E ) ) (E,\mathcal{B}(E)) ( E , B ( E )) .
The stochastic transition kernel is set as the natural kernel given the transition rules.
s 0 = ( x 0 , p 0 x , 0 , 1 , 1 { x 0 ≤ 15 } ) , s_0=(x_0,p_0^x,0,1,\mathbf{1}_{\{x_0\le15\}}), s 0 = ( x 0 , p 0 x , 0 , 1 , 1 { x 0 ≤ 15 } ) ,
where x 0 , p 0 x x_0,p_0^x x 0 , p 0 x are uniformly distributed from an area defined in § 13.2.1 .
the running reward function is set to 0 0 0 , so r : ( x , a ) ↦ 0 r:(x,a)\mapsto0 r : ( x , a ) ↦ 0
discount factor is set to β = 1 \beta=1 β = 1
terminal reward function g : E → R g:E\to\mathbb{R} g : E → R is defined as
g ( ( x t , p t x , k t , r t , i t ) ) : = 1 { i t = 0 } , g((x_t,p_t^x,k_t,r_t,i_t)):=\mathbf{1}_{\{i_t=0\}}, g (( x t , p t x , k t , r t , i t )) := 1 { i t = 0 } ,
Remark 4.2.3. We have added the round number r t r_t r t in the state space because the TD3 algorithm does not change the policy depending on the round. By adding the round number to the state space, it may depend on the round. Additionally, the information i t i_t i t is added, whether the single electron has crashed into the septum-sheet or not.
The terminal reward is 1 if the electron survived the 1000 rounds, otherwise it is 0.
Problem Modelling
1000-Electron Kick
For the 1000 electron kick, we consider the following Partially Observable Markov Decision Model with planning horizon N = 1000 N = 1000 N = 1000 with
E X × E Y : = ( R 2 × R 4 × { 0 , 1 } , × { 0 , … , 1000 } ) × ( ( R 2 × { 0 , 1 } ) 1000 × { 0 , 1 } ) , E_X \times E_Y := \left(\mathbb{R}^{2} \times\mathbb{R}^{4} \times\{0,1\}, \times\{0,\ldots,1000\}\right) \times\left((\mathbb{R}^{2} \times\{0,1\})^{1000} \times\{0,1\}\right), E X × E Y := ( R 2 × R 4 × { 0 , 1 } , × { 0 , … , 1000 } ) × ( ( R 2 × { 0 , 1 } ) 1000 × { 0 , 1 } ) ,
where the observable part ( μ , I , k , r ) ∈ E X (\mu,\mathcal{I},k,r) \in E_X ( μ , I , k , r ) ∈ E X consists of the empirical mean of the x / p x x/p^x x / p x -values μ ∈ R 2 \mu\in\mathbb{R}^{2} μ ∈ R 2 , a shape description of the electron cloud I ∈ R 4 \mathcal{I} \in\mathbb{R}^{4} I ∈ R 4 , the information whether the kicker has already been activated k k k and a round number r ∈ { 0 , … , 1000 } r \in\{0,\ldots,1000\} r ∈ { 0 , … , 1000 } .
The non-observable part ( ( ( x l , p l x ) , i l ) l = 1 1000 , k ) ∈ E Y \left(((x_l,p^x_l),i_l)_{l=1}^{1000},k\right) \in E_Y ( (( x l , p l x ) , i l ) l = 1 1000 , k ) ∈ E Y consists of the x-position x l x_l x l , the direction of flight p l x p^x_l p l x and the information i l i_l i l whether the electron with number l ∈ { 1 , … , 1000 } l \in\{1,\ldots,1000\} l ∈ { 1 , … , 1000 } has crashed against the septum-sheet or not. The number k k k describes whether the kicker has already been activated or not.
Action space A : = [ − 1 , 1 ] A := [-1,1] A := [ − 1 , 1 ] with Borel σ \sigma σ -algebra A : = B ( [ − 1 , 1 ] ) \mathcal{A} := \mathcal{B}([-1,1]) A := B ([ − 1 , 1 ])
To define the stochastic transition kernel p p p , consider the following transitions of the non-observable space between time steps. Let T \mathcal{T} T be the round-to-round transition function defined in section 3.3. For a state s t = ( ( ( x l t , p x , l t ) , i l t ) l = 1 1000 , k t ) ∈ E Y s_t = \left(((x_l^t,p^t_{x,l}),i_l^t)_{l=1}^{1000},k_t\right) \in E_Y s t = ( (( x l t , p x , l t ) , i l t ) l = 1 1000 , k t ) ∈ E Y , for a t ∈ { 0 , … , 999 } t \in\{0,\ldots,999\} t ∈ { 0 , … , 999 } and action a t ∈ A a_t \in A a t ∈ A the state in time step t + 1 t+1 t + 1 follows the rules for all l = 1 , … , 100 l=1,\ldots,100 l = 1 , … , 100 :
a ~ t = ( a t + ε t a ) 1 { a t ≠ 0 } \tilde{a}_t = (a_t+\varepsilon_t^a)\mathbb{1}_{\{a_t\ne0\}} a ~ t = ( a t + ε t a ) 1 { a t = 0 }
( x l t + 1 , p x , l t + 1 ) = T ( a ~ t ( 1 − k t ) , x l t , p x , l t ) + ( ε t x , ε t p x ) (x_l^{t+1},p_{x,l}^{t+1}) = \mathcal{T}(\tilde{a}_t(1-k_t),x_l^t,p_{x,l}^t)+(\varepsilon_t^x,\varepsilon_t^{p_x}) ( x l t + 1 , p x , l t + 1 ) = T ( a ~ t ( 1 − k t ) , x l t , p x , l t ) + ( ε t x , ε t p x )
i l t + 1 = max { i l t , 1 { x l t + 1 ≥ 15 m m } } i_l^{t+1} = \max\{i_l^t,\mathbb{1}_{\{x_l^{t+1}\ge15\mathrm{mm}\}}\} i l t + 1 = max { i l t , 1 { x l t + 1 ≥ 15 mm } }
k t + 1 = max { k t , 1 { a t ≠ 0 } } k_{t+1} = \max\{k_t,\mathbb{1}_{\{a_t\ne0\}}\} k t + 1 = max { k t , 1 { a t = 0 } }
where ε t a , ε t x \varepsilon_t^a,\varepsilon_t^x ε t a , ε t x and ε t p x \varepsilon_t^{p_x} ε t p x are normal distributed independent noises in R \mathbb{R} R and in particular ε t x , ε t p x \varepsilon_t^x,\varepsilon_t^{p_x} ε t x , ε t p x are equal for all l l l . We then set the state s t + 1 s_{t+1} s t + 1 equal to
s t + 1 = ( ( ( x l t + 1 , p x , l t + 1 ) , i l t + 1 ) l = 1 1000 , k t + 1 ) ∈ E Y . s_{t+1} = \left(((x_l^{t+1},p_{x,l}^{t+1}),i_l^{t+1})_{l=1}^{1000},k_{t+1}\right) \in E_Y. s t + 1 = ( (( x l t + 1 , p x , l t + 1 ) , i l t + 1 ) l = 1 1000 , k t + 1 ) ∈ E Y .
The observable part is then deterministically given by
time-point t + 1 t+1 t + 1 , then we define
μ t + 1 = 1 n ∑ l = 1 i l t + 1 = 0 1000 ( x l t + 1 , p x , l t + 1 ) ∈ R 2 \mu_{t+1}=\frac{1}{n}\sum_{\substack{l=1\\ i_l^{t+1}=0}}^{1000}(x_l^{t+1},p_{x,l}^{t+1})\in\mathbb{R}^{2} μ t + 1 = n 1 l = 1 i l t + 1 = 0 ∑ 1000 ( x l t + 1 , p x , l t + 1 ) ∈ R 2
– Let ( H i j z ) i , j = 0 , … , 50 ∈ [ 0 , 1000 ] (H_{ij}^{z})_{i,j=0,\ldots,50}\in[0,1000] ( H ij z ) i , j = 0 , … , 50 ∈ [ 0 , 1000 ] be the histogram matrix around the mean μ t + 1 \mu_{t+1} μ t + 1 with window lengths z ∈ R 2 z\in\mathbb{R}^{2} z ∈ R 2 . Let H θ : R 51 , 51 → R 4 \mathcal{H}_{\theta}:\mathbb{R}^{51,51}\to\mathbb{R}^{4} H θ : R 51 , 51 → R 4 be a continuous function which may depend on parameters θ ∈ R m \theta\in\mathbb{R}^{m} θ ∈ R m , for some m ∈ N m\in\mathbb{N} m ∈ N . Then, define
I t + 1 : = H θ ( H z ) . \mathcal{I}_{t+1}:=\mathcal{H}_{\theta}(H^{z}). I t + 1 := H θ ( H z ) .
The observable part is then given by o t + 1 = ( μ t + 1 , I t + 1 , k t + 1 , t + 1 ) ∈ E X o_{t+1}=(\mu_{t+1},\mathcal{I}_{t+1},k_{t+1},t+1)\in E_X o t + 1 = ( μ t + 1 , I t + 1 , k t + 1 , t + 1 ) ∈ E X . The stochastic transition kernel is set as the natural kernel given the transition rules.
s 0 = ( ( ( x l , p x , l ) , 0 ) l = 1 1000 , 0 ) ∈ E Y s_0=\left(\left((x_l,p_{x,l}),0\right)_{l=1}^{1000},0\right)\in E_Y s 0 = ( ( ( x l , p x , l ) , 0 ) l = 1 1000 , 0 ) ∈ E Y
where all x l , p x , l x_l,p_{x,l} x l , p x , l are sampled from a normal distribution with mean uniformly sampled from the area defined in § 13.2.1 and the covariance matrix
Σ = ( 0.00112 0 0 6.29 ⋅ 10 − 5 ) \Sigma=
\begin{pmatrix}
0.00112 & 0\\
0 & 6.29\cdot10^{-5}
\end{pmatrix} Σ = ( 0.00112 0 0 6.29 ⋅ 1 0 − 5 )
in meters and rad. An explanation of why this covariance matrix was chosen can be found in subsection 5.1.1.
the running reward function is set to 0 0 0 , so r : ( x , a ) ↦ 0 r:(x,a)\mapsto0 r : ( x , a ) ↦ 0
g ( o t , s t ) : = ∑ l = 1 1000 1 { i l t = 0 } , g(o_t,s_t):=\sum_{l=1}^{1000}\mathbb{1}_{\{i_l^t=0\}}, g ( o t , s t ) := l = 1 ∑ 1000 1 { i l t = 0 } ,
for all s t = ( ( ( x l t , p x , l t ) , i l t ) l = 1 1000 , k t ) ∈ E Y s_t=\left(\left((x_l^t,p_{x,l}^t),i_l^t\right)_{l=1}^{1000},k_t\right)\in E_Y s t = ( ( ( x l t , p x , l t ) , i l t ) l = 1 1000 , k t ) ∈ E Y and o t ∈ E X o_t\in E_X o t ∈ E X .
Remark 4.2.4. The function H θ \mathcal{H}_{\theta} H θ in the definition of I t + 1 \mathcal{I}_{t+1} I t + 1 is used to describe what the distribution of the electrons looks like. There are a number of ways to do this. For example, one could calculate the covariance matrix or some of the stochastic moments of the distribution. In our calculations we trained a convolutional neural network, that was given the histogram matrix and returned a 4-dimensional vector, with the goal of maximising the reward.
One-step 1000-Electron Kick
Now, we slightly modify the 1000-electron kick to a one-step 1000-electron kick. We do this, by considering the following Partially Observable Markov Decision Model with planning horizon N = 1 N = 1 N = 1 with
E X × E Y : = ( R 2 × R 4 ) × ( ( R 2 × { 0 , 1 } ) 1000 ) E_X \times E_Y := \left(\mathbb{R}^{2} \times\mathbb{R}^{4}\right) \times\left(\left(\mathbb{R}^{2} \times\{0,1\}\right)^{1000}\right) E X × E Y := ( R 2 × R 4 ) × ( ( R 2 × { 0 , 1 } ) 1000 )
where the observable part ( μ , I ) ∈ E X (\mu,\mathcal{I}) \in E_X ( μ , I ) ∈ E X consists of the empirical mean of the x / p x x/p^x x / p x values μ ∈ R 2 \mu\in\mathbb{R}^{2} μ ∈ R 2 , a shape description of the electron cloud I ∈ R 4 \mathcal{I} \in\mathbb{R}^{4} I ∈ R 4 . The non-observable part ( ( x l , p l x ) , i l ) l = 1 1000 ∈ E Y \left((x_l,p_l^x),i_l\right)_{l=1}^{1000} \in E_Y ( ( x l , p l x ) , i l ) l = 1 1000 ∈ E Y consists of the x-position x l x_l x l , the direction of flight p l x p_l^x p l x and the information i l i_l i l whether the electron with number l ∈ { 1 , … , 1000 } l \in\{1,\ldots,1000\} l ∈ { 1 , … , 1000 } , has crashed against the septum-sheet or not.
Action space A : = [ − 1 , 1 ] × [ − 1 , 1 ] A := [-1,1] \times[-1,1] A := [ − 1 , 1 ] × [ − 1 , 1 ] with Borel σ \sigma σ -algebra A : = B ( A ) \mathcal{A} := \mathcal{B}(A) A := B ( A ) . For an action a = ( a 1 , a 2 ) a = (a^1,a^2) a = ( a 1 , a 2 ) the number a 1 ∈ [ − 1 , 1 ] a^1 \in[-1,1] a 1 ∈ [ − 1 , 1 ] , is used to determine in which round the electrons are kicked. Let a ~ 1 : = ( a 1 + 1 ) ⋅ 5 \tilde{a}^{1} := (a^1 + 1) \cdot5 a ~ 1 := ( a 1 + 1 ) ⋅ 5 , then the round r r r in which the electrons are kicked is given by
r = a ~ 1 + ε r = \tilde{a}^{1} + \varepsilon r = a ~ 1 + ε
where ε ∼ Ber ( a ~ 1 − a ~ 1 ‾ ) \varepsilon\sim\operatorname{Ber}\left(\tilde{a}^{1} - \underline{\tilde{a}^{1}}\right) ε ∼ Ber ( a ~ 1 − a ~ 1 ) distributed. With a a a we denote the operation to round down a a a to the next integer. The number a 2 ∈ [ − 1 , 1 ] a^2 \in[-1,1] a 2 ∈ [ − 1 , 1 ] is used for the kicker strength.
To define the stochastic transition kernel p p p , consider the following transitions of the non-observable space between time steps. Let s 0 = ( ( x l 0 , p x , l 0 ) , i l 0 ) l = 1 1000 ∈ E Y s_0 = \left((x_l^0,p_{x,l}^0),i_l^0\right)_{l=1}^{1000} \in E_Y s 0 = ( ( x l 0 , p x , l 0 ) , i l 0 ) l = 1 1000 ∈ E Y be the initial state and a 0 = ( a 1 , a 2 ) ∈ A a_0 = (a^1,a^2) \in A a 0 = ( a 1 , a 2 ) ∈ A the chosen action. Let r r r be calculated as above. Define a t = 0 a_t = 0 a t = 0 for all t ∈ { 0 , … , 1000 } ∖ { r } t \in\{0,\ldots,1000\} \setminus\{r\} t ∈ { 0 , … , 1000 } ∖ { r } and set a r = a 2 a_r = a^2 a r = a 2 . With these actions we now follow the transition rules given in 4.2.2, and let s ~ 1000 = ( ( x l 1000 , p x , l 1000 ) , i l 1000 ) l = 1 1000 ∈ E Y \tilde{s}_{1000} = \left((x_l^{1000},p_{x,l}^{1000}),i_l^{1000}\right)_{l=1}^{1000} \in E_Y s ~ 1000 = ( ( x l 1000 , p x , l 1000 ) , i l 1000 ) l = 1 1000 ∈ E Y be the last state. Then, we set the state s 1 = s ~ 1000 s_1 = \tilde{s}_{1000} s 1 = s ~ 1000 .
Model
The observable part is deterministically given for all s t ∈ E Y s_t \in E_Y s t ∈ E Y by
μ t = 1 n ∑ l = 1 i l t = 0 1000 ( x l t , p x , l t ) ∈ R 2 \mu_t = \frac{1}{n} \sum_{\substack{l=1\\ i_l^t=0}}^{1000} (x_l^t,p_{x,l}^t) \in\mathbb{R}^2 μ t = n 1 l = 1 i l t = 0 ∑ 1000 ( x l t , p x , l t ) ∈ R 2
Let ( H i j z ) i , j = 0 , … , 50 ∈ [ 0 , 1000 ] (H_{ij}^z)_{i,j=0,\ldots,50} \in[0,1000] ( H ij z ) i , j = 0 , … , 50 ∈ [ 0 , 1000 ] be the histogram matrix around the mean μ t + 1 \mu_{t+1} μ t + 1 with window lengths z ∈ R 2 z \in\mathbb{R}^2 z ∈ R 2 . Let H θ : R 51 , 51 → R 4 \mathcal{H}_\theta: \mathbb{R}^{51,51} \to\mathbb{R}^4 H θ : R 51 , 51 → R 4 be a continuous function that may depend on parameters θ ∈ R m \theta\in\mathbb{R}^m θ ∈ R m , for some m ∈ N m \in\mathbb{N} m ∈ N . Then, define
I t : = H θ ( H z ) . \mathcal{I}_t := \mathcal{H}_\theta(H^z). I t := H θ ( H z ) .
The observable part is then given by o t = ( μ t , I t ) ∈ E X o_t = (\mu_t,\mathcal{I}_t) \in E_X o t = ( μ t , I t ) ∈ E X .
The stochastic transition kernel is set as the natural kernel given the transition rules.
s 0 = ( ( ( x l , p x , l ) , 0 ) l = 1 1000 , 0 ) ∈ E Y s_0 = \left(\left((x_l,p_{x,l}),0\right)_{l=1}^{1000},0\right) \in E_Y s 0 = ( ( ( x l , p x , l ) , 0 ) l = 1 1000 , 0 ) ∈ E Y
where all x l , p x , l x_l,p_{x,l} x l , p x , l are sampled from a normal distribution with mean uniformly sampled from the area defined in section 3.4.1 and the covariance matrix
Σ = ( 0.00112 0 0 6.29 ⋅ 10 − 5 ) \Sigma=
\begin{pmatrix}
0.00112 & 0 \\
0 & 6.29 \cdot10^{-5}
\end{pmatrix} Σ = ( 0.00112 0 0 6.29 ⋅ 1 0 − 5 )
in meters and rad.
the running reward function is set to 0 0 0 , so r : ( x , a ) ↦ 0 r:(x,a)\mapsto0 r : ( x , a ) ↦ 0
g ( o t , s t ) : = ∑ l = 1 1000 1 { i l t = 0 } , g(o_t,s_t) := \sum_{l=1}^{1000} 1_{\{i_l^t=0\}}, g ( o t , s t ) := l = 1 ∑ 1000 1 { i l t = 0 } ,
for all s t = ( ( x l t , p x , l t ) , i l t ) l = 1 1000 ∈ E Y s_t = \left((x_l^t,p_{x,l}^t),i_l^t\right)_{l=1}^{1000} \in E_Y s t = ( ( x l t , p x , l t ) , i l t ) l = 1 1000 ∈ E Y and o t ∈ E X o_t \in E_X o t ∈ E X .
Remark 4.2.5. The advantage of the one-step kick is that it can be realistically implemented at BESSY II.
Since the position and shape of the newly injected electrons change only slightly from one injection to the next, we can use the information from the last injection to predict in which round and with which kicker strength the non-linear kicker should be used in the next injection.
Summary
In this chapter, we have seen 4 different ways of formulating the injection process. At the beginning of chapter 4.2, we introduced the first model. It showed the injection for a distribution of electrons. Although, only a finite number of electrons are injected each time since the sensor data is given as a histogram plot, we decided to model it as a distribution of electrons. We have shown the dynamics of the problem and described the final reward.
The following 3 models are the models on which we applied reinforcement learning algorithms to find good policies. They were designed to have a low dimensional state space.
First, we described the single electron kick in subsection 4.2.1. In each round, we obtained the x x x and p x p_x p x information of an electron and could decide if we wanted to activate the non-linear kicker and if so with what strength.
Second, we described the 1000-step 1000-electron kick in subsection 4.2.2. In this model we obtained some information about the shape of the distribution of electrons and the mean values for x x x and p x p_x p x , in each round. With that we could decide once again in each round if we wanted to kick the electrons and with what strength.
Third, we described the 1-step 1000-electron injection in subsection 4.2.3. Here, we only had the information about the shape and mean of the electrons in the very first round. Once again, we could use this information to decide in which round and with what strength we want to kick the electrons. We saw there, how to make the round decision a continuous action value, as this is needed for the DDPG and TD3 algorithms.
In section 5.2, we showed the performance of reinforcement learning algorithms on the different models.
Calculations
In this chapter, we investigate all the steps needed to train the reinforcement learning algorithms. We start with how we added stochasticity to the "drift-kick" simulation of BESSY II, explained in § 13.1 and how we made the simulation significantly faster, by approximating the environment.
Then, we describe small modifications we made on the Markov Decision Models explained in section 4.2. Finally, we show the best results in all the different models. The programming reference can be found under the url https://tubcloud.tu-berlin.de/s/RdKEm7sw9e5gyzY .
Implementation overview
Introduction of Stochasticity
In § 13.1 , we discovered how to create a simulation of BESSY II. We assume that the round-to-round behaviour function T \mathcal{T} T is known. In the explanation of the Markov Decision Models in section 4.2, we argued to add noise to the p x p_x p x and x x x values of the electrons in each round, as well as to the kicker strength. In this subsection, we show how the noises are distributed.
All noise is zero mean normally distributed with the following standard deviations:
Table 1.
The amount of noise added to the electrons is the highest in the first round. This is because the magnets that guide the electrons close to the septum-sheet may create an additional unwanted influence on the electrons.
In every other round we also add noise to account for measurement errors and other possible unwanted influences from magnets. Additionally, we add noise to the non-linear kicker strength, since the desired strength can never be set exactly.
The last missing stochastic element is the distribution of the 1000 electrons, which we need in the 1000-electron kick and the one-step 1000-electron kick. We know that in the first round the distribution of the newly injected electrons has standard deviations of σ x = 0.00112 m \sigma_x = 0.00112\mathrm{m} σ x = 0.00112 m and σ p x = 6.29 ⋅ 10 − 5 r a d \sigma_{p_x} = 6.29 \cdot10^{-5}\mathrm{rad} σ p x = 6.29 ⋅ 1 0 − 5 rad . See the PhD-Thesis Transverse Resonance Island Buckets at BESSY II -A new Bunch Separation Scheme- by Felix Armborst [23 ] , section 4.2). Also, we assume that there is no correlation between both values.
Creating the approximated simulation
In this subsection, we investigate the creation of our own approximated simulation of non-linear kicker problem at BESSY II. Since the "drift-kick" simulation, see [21 ] , took 180 seconds to simulate 1000 rounds for 1000 electrons, the idea is to create a similar but much faster environment. It is used to find good hyperparameters within a short time. Then, only the training for the best performing hyperparameters is re-executed using on original slower environment. In subsection 5.2.2, we will show that the faster simulation is so close to the real simulation that good policies in the faster simulation also work well in the real simulation.
We have divided our analysis into two parts. In the first, we will consider how the round-to-round behaviour without the non-linear kicker influence can be approximated. In the second, we are interested in what to do when the non-linear kicker is activated.
Round-to-round behaviour
We have approximated the round-to-round behaviour without the non-linear kicker by interpolation. Let x = ( x 1 , … , x m ) \mathbf{x} = (x_1,\ldots,x_m) x = ( x 1 , … , x m ) and p x = ( p 1 x , … , p n x ) \mathbf{p}^x = (p^x_1,\ldots,p^x_n) p x = ( p 1 x , … , p n x ) be a grid (sorted and equidistant) over all realistic x \mathbf{x} x and p x \mathbf{p}^x p x values. Now calculate for all x i , p j x x_i,p^x_j x i , p j x the actual round-to-round behaviour x ~ i , p ~ j x = T ( 0 , x i , p j x ) \widetilde{x}_i,\widetilde{p}^x_j = T(0,x_i,p^x_j) x i , p j x = T ( 0 , x i , p j x ) , with the "drift-kick" simulation, provided by [21 ] .
If we want to compute the round-to-round behaviour for new values x , p x x,p^x x , p x , we can do this in the following way:
Assume x ∈ [ x 1 , x m ] x \in[x_1,x_m] x ∈ [ x 1 , x m ] and p x ∈ [ p 1 x , p n x ] p^x \in[p^x_1,p^x_n] p x ∈ [ p 1 x , p n x ] . Otherwise, we assume that the electron is so far out, that it is lost.
Let i , j i,j i , j be the indices, such that x ∈ [ x i , x i + 1 ] x \in[x_i,x_{i+1}] x ∈ [ x i , x i + 1 ] and p x ∈ [ p j x , p j + 1 x ] p^x \in[p^x_j,p^x_{j+1}] p x ∈ [ p j x , p j + 1 x ] . We call b = { ( x i , p j x ) , ( x i , p j + 1 x ) , ( x i + 1 , p j x ) , ( x i + 1 , p j + 1 x ) } \mathbf{b}=\{(x_i,p^x_j),(x_i,p^x_{j+1}),(x_{i+1},p^x_j),(x_{i+1},p^x_{j+1})\} b = {( x i , p j x ) , ( x i , p j + 1 x ) , ( x i + 1 , p j x ) , ( x i + 1 , p j + 1 x )} the set of all border points.
Calculate the euclidean distances of ( x , p x ) (x,p^x) ( x , p x ) to all border points. Let d ∈ R 4 \mathbf{d}\in\mathbb{R}^4 d ∈ R 4 be the distances (sorted as in the definition of b \mathbf{b} b ).
Normalise the distance vector d \mathbf{d} d by setting d n : = d ∥ d ∥ 2 \mathbf{d}_n:=\frac{\mathbf{d}}{\lVert\mathbf{d}\rVert_2} d n := ∥ d ∥ 2 d .
As closer points have smaller distances, but are probably more accurate, define
d r = ( 1 − d n ) ∥ ( 1 − d n ) ∥ 2 . \mathbf{d}_r=\frac{(1-\mathbf{d}_n)}{\lVert(1-\mathbf{d}_n)\rVert_2}. d r = ∥( 1 − d n ) ∥ 2 ( 1 − d n ) .
Let x ~ : = { T ( 0 , x ~ , p ~ x ) ∣ x ∣ ( x ~ , p ~ x ) ∈ b } \widetilde{\mathbf{x}}:=\{\mathcal{T}(0,\widetilde{x},\widetilde{p}^x)|_x\mid(\widetilde{x},\widetilde{p}^x)\in\mathbf{b}\} x := { T ( 0 , x , p x ) ∣ x ∣ ( x , p x ) ∈ b } and p ~ x : = { T ( 0 , x ~ , p ~ x ) ∣ p x ∣ ( x ~ , p ~ x ) ∈ b } \widetilde{\mathbf{p}}^x:=\{\mathcal{T}(0,\widetilde{x},\widetilde{p}^x)|_{p^x}\mid(\widetilde{x},\widetilde{p}^x)\in\mathbf{b}\} p x := { T ( 0 , x , p x ) ∣ p x ∣ ( x , p x ) ∈ b } be the sets of the new x- and px-values of the border points. Assume that we can treat these sets as vectors (sorted as in the definition of b \mathbf{b} b ).
The transitioned x- and px-values starting at x , p x x,p^x x , p x can be calculated using:
x ′ = d r T x ~ and p x ′ = d r T p ~ x . x'=\mathbf{d}_r^{T}\widetilde{\mathbf{x}}\quad\text{and}\quad p^{x'}=\mathbf{d}_r^{T}\widetilde{\mathbf{p}}^x. x ′ = d r T x and p x ′ = d r T p x .
With this method, we have found a fast way to approximate the transition function T ( 0 , ⋅ , ⋅ ) \mathcal{T}(0,\cdot,\cdot) T ( 0 , ⋅ , ⋅ ) . Note that the smaller the grid size, the better the approximation, and that the calculation for 1000 electrons can be nicely parallelised in NumPy, see [24 ] .
Non-linear kicker behaviour
Now, we show what was done to approximate the non-linear kicker behaviour.
The first thing we did was to fit an easy to evaluate function to the electron survival rate seen.
Calculations
In Figure 3.18 , one can see which function was fitted to the electron survival rate.
Note that we used the scaling factor 985 in the approximation shown in Figure 5.1 , since the real injection will never reach 100% efficiency.
Figure 5.1. Extended Figure 3.18 . The orange line maps a kicker strength α \alpha α to 985 ⋅ exp ( − ( 14.5 ⋅ ( α − α ∗ ) ) 4 ) 985 \cdot\exp(-(14.5 \cdot(\alpha-\alpha^*))^4) 985 ⋅ exp ( − ( 14.5 ⋅ ( α − α ∗ ) ) 4 ) , where α ∗ = − 0.1075 \alpha^*=-0.1075 α ∗ = − 0.1075 is the optimal kicker strength. The value represents: How many electrons out of 1000 survive the injection, given the kicker strength. Note that the optimal kicker strength α ∗ \alpha^* α ∗ depends on the x , p x x,p^x x , p x position at the kicker, see § 14.0.1 for details.
We have now combined the models shown in the Figure 3.16 , Figure 3.17 and Figure 5.1 to determine the electron survival probability at current x x x - and p x p^x p x -values x x x , p x p^x p x and kicker strength α \alpha α . Figure 3.16 shows whether the electron could be successfully kicked given the current x x x - and p x p^x p x -values at the septum sheet. Figure 3.17 shows the corresponding optimal kicker strengths and Figure 5.1 shows the injection probability for different kicker strengths. We have approximated the non-linear kicker usage for a single electron with x x x - and p x p^x p x -values x x x , p x p^x p x and kicker strength α \alpha α in the following way:
For the values x x x , p x p^x p x we checked if one of the border points in the grid shown in Figure 3.16 survived the kick, i.e. had value 1000. If not, we set the injection probability to 0.
In a similar way to approximating the round-to-round behaviour explained above, we approximated the optimal kicker strength by interpolation (the optimal kicker strength for all not survived border points have been set to -1, such that it remained well-defined. One could have ignored the points and used only the survived border points, which we did not do. The way we did it was simpler and faster).
Now, using the approximation 985 ⋅ exp ( − ( 14.5 ⋅ ( α − α ∗ ) 4 ) 985 \cdot\exp(-(14.5 \cdot(\alpha-\alpha^*)^4) 985 ⋅ exp ( − ( 14.5 ⋅ ( α − α ∗ ) 4 ) from Figure 5.1 ,
where α ∗ \alpha^* α ∗ is the approximated optimal kicker strength and α \alpha α is the chosen kicker strength, we can now approximate the survival probability by dividing the value 985 ⋅ exp ( − ( 14.5 ⋅ ( α − α ∗ ) ) 4 ) 985 \cdot\exp(-(14.5 \cdot(\alpha-\alpha^*))^4) 985 ⋅ exp ( − ( 14.5 ⋅ ( α − α ∗ ) ) 4 ) by 1000.
So, we have found a way to approximate the electron survival probability in a fast way.
Note that the approximation 985 ⋅ exp ( − ( 14.5 ⋅ ( α − α ∗ ) ) 4 ) 985 \cdot\exp(-(14.5 \cdot(\alpha-\alpha^*))^4) 985 ⋅ exp ( − ( 14.5 ⋅ ( α − α ∗ ) ) 4 ) was only fitted to a single pair of x , p x x,p^x x , p x values, namely x = 16.4 m m x=16.4\mathrm{mm} x = 16.4 mm and p x = 0.0 m r a d p^x=0.0\mathrm{mrad} p x = 0.0 mrad . As an approximation, we assume that this holds for all x , p x x,p^x x , p x values.
Now, we can calculate the probability of the electrons surviving the injection at the moment the electrons are kicked. We no longer need to transition them to round 1000. This also gives us a way of simultaneously approximating the expected number of electrons that survive the injection for 1000 electrons, by summing up each individual survival probability.
Note that with this approximation and not transitioning the electrons to round 1000, we no longer follow the Markov Decision Models defined in section 4.2. We move on to show that this shortcut does not change the value functions.
From the reward iteration theorem 2.2.1, we know that
V n , π ( x ) = β n r ( x , f n ( x ) ) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x ) ) , for all x ∈ E . V_{n,\pi}(x)=\beta^n r(x,f_n(x))+\int_E V_{n+1,\pi}(x')p(dx'|x,f_n(x)),\quad\text{for all }x\in E. V n , π ( x ) = β n r ( x , f n ( x )) + ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x )) , for all x ∈ E .
Let n n n be the round in which the non-linear kicker was activated. From the definition of the Markov Decision Models in section 4.2, we know that from now on no action will affect the transitions and all rewards r r r are set to 0. Since in all further rounds the states x ′ x' x ′ are independent of the chosen action, we get
V n , π ( x ) = ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x ) ) = E [ V n + 1 , π ( x ′ ) ∣ x , f n ( x ) ] = E [ E [ V n + 2 , π ( x ′ ′ ) ∣ x ′ ] ∣ x , f n ( x ) ] = E [ V n + 2 , π ( x ′ ′ ) ∣ x , f n ( x ) ] = … = E [ g ( x ( 1000 − n ) ) ∣ x , f n ( x ) ] \begin{aligned}
V_{n,\pi}(x)&=\int_E V_{n+1,\pi}(x')p(dx'|x,f_n(x))\\
&=\mathbb{E}[V_{n+1,\pi}(x')|x,f_n(x)]\\
&=\mathbb{E}[\mathbb{E}[V_{n+2,\pi}(x'')|x']|x,f_n(x)]\\
&=\mathbb{E}[V_{n+2,\pi}(x'')|x,f_n(x)]\\
&=\ldots\\
&=\mathbb{E}[g(x^{(1000-n)})|x,f_n(x)]
\end{aligned} V n , π ( x ) = ∫ E V n + 1 , π ( x ′ ) p ( d x ′ ∣ x , f n ( x )) = E [ V n + 1 , π ( x ′ ) ∣ x , f n ( x )] = E [ E [ V n + 2 , π ( x ′′ ) ∣ x ′ ] ∣ x , f n ( x )] = E [ V n + 2 , π ( x ′′ ) ∣ x , f n ( x )] = … = E [ g ( x ( 1000 − n ) ) ∣ x , f n ( x )]
for all x ∈ E x\in E x ∈ E , which is equal to the expected amount of electrons that survive.
This allows us to stop at the moment where the kicker was activated and return the expected number of surviving electrons as reward.
We have thus created a faster simulation of the non-linear kicker problem, which we
Calculations
can use to find good hyperparameters and even use the learned policies for the actual simulation.
Adapting actions
As in the 1000-step single-electron model and the 1000-step 1000-electron model, the non-linear kicker is activated as soon as the chosen action is not equal to 0. We wanted to increase the interval where electrons are not kicked, such that waiting a round and possibly kicking the electrons in the next round would be easier for the policies to learn.
To do this, we introduced the following activation function around the chosen actions
φ ( x ) = sign ( x ) ⋅ x 4 \varphi(x) = \operatorname{sign}(x) \cdot x^4 φ ( x ) = sign ( x ) ⋅ x 4
and decided that in the interval [ − 0.16 , 0.16 ] [-0.16, 0.16] [ − 0.16 , 0.16 ] the chosen actions do not lead to the activation of the non-linear kicker. The interval limits were chosen so that a kicker activation of 0.16 4 0.16^4 0.1 6 4 leads to the change in the electrons direction of flight similar in magnitude to the added noise.
Reward design
A small change in the running reward function r r r was made to the first two models, where the information of the electrons were given in each round. In case the non-linear kicker was activated, but no electrons were in the accepted kicker area, shown in Figure 3.16 , we decided to give a small reward that would increase the closer the chosen action was to 0, such that the algorithm learns not to kick the electrons in that round.
To do this, we added two hyperparameters r 1 , r 2 r_1,r_2 r 1 , r 2 to the models, which we call reward design parameters. We set the reward function r r r to
r 1 − r 2 ⋅ ∣ α ∣ , r_1-r_2\cdot|\alpha|, r 1 − r 2 ⋅ ∣ α ∣ ,
where α \alpha α is the chosen kicker strength, but only in the case where the kicker was activated and all electrons were outside the kick-able area. For the hyperparameter search we allowed the values r 1 ∈ [ − 50 , 50 ] r_1 \in[-50,50] r 1 ∈ [ − 50 , 50 ] and r 2 ∈ [ 0 , 50 ] r_2 \in[0,50] r 2 ∈ [ 0 , 50 ] .
Programming results
In this section, we will present the best performing policies that we have been able to train. All policies were found using the TD3 algorithm described in subsection 2.4.2 and have been optimised using the tree-structured parzen estimator hyperparameter search algorithm, described in 2.6.2. We also made the small adjustments described in subsections 5.1.3 and 5.1.4, where we added an activation function around the action and changed the reward design in a specific case.
1000-Step Single-Electron Model
We start with the model explained in subsection 4.2.1. In this model we get the information of the x x x and p x p_x p x value of the electron in each round and can decide if we want to use the non-linear kicker and if so, with which kicker strength.
The following figures show the performance of the best trained policy on the injection area. The first plot shows the reward, the second the round in which the different electrons were been kicked.
Calculations
In Figure 5.2 , we can see that the performance of the model in the injection area is very good. In two smaller areas the electrons cannot be successfully injected. In Figure 5.3 , we can see that rounds 0,1,3 and 4 have been used.
Figure 5.2. Model performance of the best policy on the injection area. The performance was checked on the deterministic version of the environment to make the results comparable. The x , p x x,p_x x , p x values are the initial values at the septum sheet. The performance shown is 1000 times the final reward. The average score over the whole injection area is 875 out of 1000 possible.
Figure 5.3. Corresponding rounds for the model shown in Figure 5.2 .
For the training we used the following hyperparameters:
neural network (NN) shape of the policy network: (256, 128)
NN-shape of the value function network: (32, 32)
learning rate: 0.002722
batch size 64
number of runs before starting learning: 250
τ = 0.005 \tau= 0.005 τ = 0.005
action-noise: Ornstein-Uhlenbeck noise with standard variation: 0.377
reward design parameters r 1 = 11 , r 2 = 7 r_1 = 11,r_2 = 7 r 1 = 11 , r 2 = 7
discount factor γ = 1.3552 \gamma= 1.3552 γ = 1.3552 .
Note that we did not use a discount factor (γ = 1 \gamma=1 γ = 1 ) to measure the performance. For the training process we have seen that it makes a difference and we have had the best results with discount factors greater than 1. This is very unusual, as the discount factor is usually chosen between 0 and 1. In our case, it helped the model to explore later rounds to kick the electrons.
1000-Step 1000-Electron Model
We continue with the model explained in subsection 4.2.2. Here we have the information of the x x x and p x p_x p x means, and the shape of the 1000 electrons in each round and can decide if we want to use the non-linear kicker and if so, with which kicker strength.
In this subsection, we look at some additional analysis that can also be applied to the next model. First, we show the performance of the best trained agent. Then, we compare it with the theoretical best performing policy and finally, we show how the agent performs in the real simulation.
The following figures show the performance of the best trained policy on the injection area. The first plot shows the reward, the second the round in which the different electrons were kicked.
Calculations
In Figure 5.4 , we can see that the performance of the model in the injection area is good. The area close to the septum sheet is not injected as successfully. The reason for this is that when the x-mean is close to 15mm, half of the electrons are already lost in the septum-sheet, before we are able to use the non-linear kicker. Similar to the performance of the model in the single-electron case, the electrons with x-mean greater than 20.5mm are not injected successfully. In Figure 5.5 , we can see that the rounds 0,2,3 and 4 have been used.
Figure 5.4. Model performance of the best policy on the injection area. The performance was checked on the deterministic version of the environment to make the results comparable. The x,px values show the mean of the distribution of electrons at the septum sheet. The performance shown corresponds to how many of the 1000 electrons survived the injection. The mean value over the whole injection area is 644.
Figure 5.5. Corresponding rounds for the model shown in Figure 5.4 .
The following hyperparameters were used for training:
NN-shape of the policy network: ( 256 , 128 ) (256, 128) ( 256 , 128 )
NN-shape of the value function network: ( 512 ) (512) ( 512 )
learning rate: 0.000464
batch size 64
number of runs before starting learning: 250
τ = 0.005 \tau= 0.005 τ = 0.005
action-noise: Ornstein-Uhlenbeck noise with standard variation: 0.841
reward design parameters r 1 = 11.129 , r 2 = 6.67 r_1 = 11.129, r_2 = 6.67 r 1 = 11.129 , r 2 = 6.67
discount factor γ = 1.463 \gamma= 1.463 γ = 1.463 .
Again, we did not use a discount factor ( γ = 1 ) (\gamma=1) ( γ = 1 ) in the performance measure. As a continuous transformation function H θ : R 51 , 51 → R 4 H_\theta: \mathbb{R}^{51,51} \to\mathbb{R}^{4} H θ : R 51 , 51 → R 4 , which takes the histogram plots
Programming results
as an input, we trained a convolutional neural network with the continuous ReLU activation function.
The following code shows the used convolutional neural network:
from torch import nn
cnn_used = nn.Sequential(
nn.Conv2d(1, 8, kernel_size=6, stride=2, padding=0),
nn.ReLU(),
nn.MaxPool2d(2),
nn.Conv2d(8, 4, kernel_size=3, stride=1, padding=0),
nn.ReLU(),
nn.MaxPool2d(2),
nn.Conv2d(4, 4, kernel_size=2, stride=1, padding=0),
nn.ReLU(),
nn.Conv2d(4, 2, kernel_size=2, stride=1, padding=0),
nn.ReLU(),
nn.Flatten(),
nn.Linear(8, 4))
In each nn.Conv2d the first input is the number of input channels, the second input is the number of output channels. The input of all nn.MaxPool2d is the window length. Note that we used multiple times in our code an even window length. As in our definition of CNNs (definition 2.4.4) only odd windows lengths were allowed, we refer to the paper A guide to convolution arithmetic for deep learning by V. Dumoulin and F. Visin [25 ] to see how it is used.
To evaluate the performance, we calculated the theoretical optimal performance on the injection area for the 1000 electron injections. For each combination of x and px means, we calculated the optimal kicker strength in each round and how many electrons would survive the injection.
The following results were obtained:
Calculations
Figure 5.7. Theoretical best performance on the injection area. The performance was checked on the deterministic version of the environment to make the results comparable. The x,p x p_x p x values show the mean of the distribution of electrons at the septum sheet. The performance shown corresponds to how many of the 1000 electrons survived the injection. The mean value over the whole injection area is 676.57.
Figure 5.8. Corresponding rounds for the model shown in figure 5.7.
We observe that the performance of our trained policy is close to the performance of the optimal policy. The optimal policy has lower scores for the electrons that are far outside than the trained policy. The rounds chosen to activate the non-linear kicker are slightly different.
Now, we show the performance of the model on the real simulation we have approximated, to ensure that the approximated simulation is close to the "drift-kick" simulation.
Calculations
Figure 5.10. Corresponding rounds for the model shown in Figure 5.9 .
Figure 5.9. Performance of best trained model on the injection area in the "drift kick" simulation. The performance was checked on the deterministic version of the "drift kick" simulation to make the results comparable. The x , p x x,p_x x , p x values show the mean of the distribution of electrons at the septum sheet. The performance shown corresponds to how many of the 1000 electrons survived the injection. The mean value over the whole injection area is 727.7.
We see that the performances are similar. The total score for the injection area is 727.7. This is even higher than the performance in the approximated simulation. However, in the regions where the injection round changes, the performance is worse. These observations suggest that the approximation of the non-linear kicker behaviour is not exact. In some regions where the optimal kicker strength changes rapidly, see Figure 3.17 , the plateau drop in electron survival probability should have been faster, see Figure 5.1 . In other regions, where the optimal kicker strength changes slowly, it could have been more relaxed. Overall, our approximation remains good, because the overall score is lower and the approximation of the round-to-round behaviour is very close.
1-Step 1000-Electron Model
We end with the model explained in subsection 4.2.1. Here we only get the information of the x and px means and the shape of the 1000 electrons in the very first round and after that we have to decide directly when to use the non-linear kicker and with which kicker strength.
The following figures show the performance of the best trained policy on the injection area. The first plot shows the reward, the second the round in which round the different electrons were kicked.
Programming results
The Figure 5.11 shows the performance of the model in the injection area. Note that the image noise seen in the figure is the result of the stochastic choice of round, described in 4.2.3. There is no noise in the lower half of the injection area in the performance Figure 5.11 , because the lower end of an action space is easier to hit by clipping operators than values in between.
Figure 5.11. Model performance of the best policy on the injection area. The performance was checked on the deterministic version of the environment to make the results comparable. The x,px values show the mean of the distribution of electrons at the septum sheet. The performance shown corresponds to how many of the 1000 electrons survived the injection. The mean value over the whole injection area is 600.
Compared to the other results, its performance is the worst. In particular, the performances for electrons with high x-value and low px values is not great.
In Figure 5.12 , we can see that the used rounds almost equals the used rounds of the best 1000-step 1000-electron case, see Figure 5.5 . For the electrons with low px values, the best 1000-step 1000-electron model used the round 4 to kick the electrons, which the model here was model able to learn. Possibly, with other hyperparameters and a longer training duration, this would have been possible.
Figure 5.12. Corresponding rounds for the model shown in Figure 5.11 .
The following hyperparameters were used for training:
NN-shape of the policy network: (256, 128)
NN-shape of the value function network: (256, 128)
learning rate: 0.001
batch size 64
number of runs before learning starts: 250
τ = 0.005 \tau= 0.005 τ = 0.005
action-noise: Ornstein-Uhlenbeck noise with standard variation: 1.4777
discount factor γ = 1 \gamma= 1 γ = 1 .
Again, no discount factor (γ = 1 \gamma=1 γ = 1 ) was used in the performance measure. We used the same convolutional neural network for the continuous transformation function H θ : R 51 , 51 → R 4 \mathcal{H}_{\theta}: \mathbb{R}^{51,51} \to\mathbb{R}^{4} H θ : R 51 , 51 → R 4 , as shown in Figure 5.6 .
Figure 5.6. Used CNN structure.
Summary
At the beginning of this chapter, we saw how we added noise to the "drift-kick" simulation to make the injection process more realistic. We then created an approximate simulation of the "drift-kick" simulation. For this approximate simulation, we approximated the round-to-round behaviour using interpolation and once the non-linear kicker was activated, we approximated the number of electrons that would survive this injection. This approximated simulation is much faster, remains precise and the noise can be added in the same way. We also found a shortcut by stopping the Markov decision process as soon as the non-linear was activated, which reduced the time needed for the simulation.
Summary
We needed this faster simulation in order to find good hyperparameters and policies in a reasonable time. For all 3 different Markov decision models, with varying degrees of complexity, we found very good performing policies. We have shown that these policies trained on the approximate simulation even work well for the "drift kick" simulation, and they show how to kick the electrons dependent on their position. Particularly, we were able to identify regions where the electrons are most likely to survive the injection.
Conclusion
This thesis started off with an introduction to reinforcement learning. We saw the definition of a Markov decision process, defined the value function and proved the Bellman equation, which allowed us to compute optimal policies. As this was not efficient for continuous action spaces, we saw the DDPG and TD3 algorithms and how they solved the problem using function approximators.
We also gave an introduction to hyperparameter search. As the performance of reinforcement learning algorithms depends heavily on how well the hyperparameters fit to the problem, we presented in § 10.2 different ways to search the hyperparameter space for good parameters.
We also defined partially observable Markov decision models and explained the difference to Markov decision models.
We then took a closer look at an application for reinforcement learning. The aim was to optimise the non-linear kicker injection at BESSY II. We looked at the physical background of BESSY II and the non-linear kicker and gave some intuition on how to use the non-linear kicker. We explained how we added stochasticity to the environment and created our own approximate simulation of the BESSY II injection.
The non-linear kicker injection was described in 3 different ways with varying degrees of complexity. For all 3 different models we found very good policies.
In particular, the 1-step 1000-electron model, where the policies decided the kicker activation round and strength uses only the information from the electrons in round 0, could be used for the real injection at BESSY II, as this environment reflects the real machine capabilities of BESSY II. Since the shape and position of the newly injected electrons typically change only slightly from one injection to the next, the information from the last injection could be used to find the optimal activation round and strength.
Note that before actually applying a trained policy on the real machine BESSY II, one would need to train the policy to be more robust in case of environment changes.
In addition, another reinforcement learning agent could be trained to use the magnetic steerers, leading the electrons to the septum-sheet, to always steer the electrons into a region of high injection efficiency.
The results show that it is possible to train reinforcement learning agents to optimise the non-linear kicker injection. The best trained 1-step 1000-electron policy is now ready to be tested on the BESSY II machine.
Bibliography