Eine Einführung in Policy Gradients mit Cartpole and Doom

Dieser Artikel ist Teil des Deep Reinforcement Learning Course mit Tensorflow? ️. Überprüfen Sie den Lehrplan hier.

In den letzten beiden Artikeln über Q-Learning und Deep Q Learning haben wir mit wertbasierten Verstärkungslernalgorithmen gearbeitet. Um zu entscheiden, welche Aktion in einem bestimmten Zustand ausgeführt werden soll, führen wir die Aktion mit dem höchsten Q-Wert aus (maximal erwartete zukünftige Belohnung, die ich in jedem Zustand erhalten werde). Infolgedessen existiert beim wertbasierten Lernen eine Richtlinie nur aufgrund dieser Aktionswertschätzungen.

Heute lernen wir eine richtlinienbasierte Verstärkungstechnik namens Policy Gradients.

Wir werden zwei Agenten implementieren. Der erste wird lernen, die Messlatte im Gleichgewicht zu halten.

Der zweite wird ein Agent sein, der lernt, in einer Doom-feindlichen Umgebung zu überleben, indem er Gesundheit sammelt.

Bei richtlinienbasierten Methoden lernen wir nicht eine Wertefunktion, die uns die erwartete Summe der Belohnungen für einen Status und eine Aktion angibt, sondern direkt die Richtlinienfunktion, die den Status einer Aktion zuordnet (wählen Sie Aktionen aus, ohne eine Wertefunktion zu verwenden).

Dies bedeutet, dass wir direkt versuchen, unsere Richtlinienfunktion π zu optimieren, ohne uns um eine Wertefunktion zu kümmern. Wir werden π direkt parametrisieren (wählen Sie eine Aktion ohne Wertfunktion aus).

Natürlich können wir eine Wertefunktion verwenden, um die Richtlinienparameter zu optimieren. Die Wertefunktion wird jedoch nicht zum Auswählen einer Aktion verwendet.

In diesem Artikel erfahren Sie:

  • Was ist Policy Gradient und seine Vor- und Nachteile?
  • So implementieren Sie es in Tensorflow.

Warum richtlinienbasierte Methoden verwenden?

Zwei Arten von Richtlinien

Eine Politik kann entweder deterministisch oder stochastisch sein.

Eine deterministische Richtlinie ist eine Richtlinie, die den Status Aktionen zuordnet. Sie geben ihm einen Status und die Funktion gibt eine auszuführende Aktion zurück.

Deterministische Richtlinien werden in deterministischen Umgebungen verwendet. Dies sind Umgebungen, in denen die ergriffenen Maßnahmen das Ergebnis bestimmen. Es gibt keine Unsicherheit. Wenn Sie beispielsweise Schach spielen und Ihren Bauern von A2 auf A3 verschieben, sind Sie sicher, dass sich Ihr Bauer auf A3 bewegt.

Andererseits gibt eine stochastische Politik eine Wahrscheinlichkeitsverteilung über Aktionen aus.

Es bedeutet , dass anstelle des Seins sicher handlungs ein (zum Beispiel links), gibt es eine Wahrscheinlichkeit , wir einen anderen nehmen werden (in diesem Fall 30% , dass wir nach Süden nehmen).

Die stochastische Politik wird angewendet, wenn die Umgebung unsicher ist. Wir nennen diesen Prozess einen partiell beobachtbaren Markov-Entscheidungsprozess (POMDP).

Meistens verwenden wir diese zweite Art von Richtlinie.

Vorteile

Aber Deep Q Learning ist wirklich großartig! Warum politikbasierte Lernmethoden zur Stärkung?

Die Verwendung von Richtlinienverläufen bietet drei Hauptvorteile.

Konvergenz

Zum einen haben richtlinienbasierte Methoden bessere Konvergenzeigenschaften.

Das Problem bei wertbasierten Methoden ist, dass sie während des Trainings eine große Schwingung haben können. Dies liegt daran, dass sich die Wahl der Aktion bei einer willkürlich kleinen Änderung der geschätzten Aktionswerte dramatisch ändern kann.

Auf der anderen Seite folgen wir beim Richtliniengradienten einfach dem Gradienten, um die besten Parameter zu finden. Wir sehen bei jedem Schritt eine reibungslose Aktualisierung unserer Richtlinien.

Da wir dem Gradienten folgen, um die besten Parameter zu finden, konvergieren wir garantiert auf ein lokales Maximum (Worst Case) oder ein globales Maximum (Best Case).

Richtlinienverläufe sind in hochdimensionalen Aktionsräumen effektiver

Der zweite Vorteil besteht darin, dass Richtlinienverläufe in hochdimensionalen Aktionsräumen oder bei Verwendung kontinuierlicher Aktionen effektiver sind.

Das Problem beim Deep Q-Learning besteht darin, dass ihre Vorhersagen für jede mögliche Aktion in jedem Zeitschritt unter Berücksichtigung des aktuellen Status eine Punktzahl (maximal erwartete zukünftige Belohnung) zuweisen.

Aber was ist, wenn wir eine unendliche Handlungsmöglichkeit haben?

Zum Beispiel können Sie mit einem selbstfahrenden Auto in jedem Zustand eine (nahezu) unendliche Auswahl an Aktionen haben (Drehen des Rads um 15 °, 17,2 °, 19,4 °, Hupen…). Wir müssen für jede mögliche Aktion einen Q-Wert ausgeben!

Auf der anderen Seite passen Sie bei richtlinienbasierten Methoden die Parameter einfach direkt an: Dank dessen beginnen Sie zu verstehen, wie hoch das Maximum sein wird, anstatt das Maximum bei jedem Schritt direkt zu berechnen (zu schätzen).

Richtlinienverläufe können stochastische Richtlinien lernen

Ein dritter Vorteil ist, dass ein Richtliniengradient eine stochastische Richtlinie lernen kann, während Wertfunktionen dies nicht können. Dies hat zwei Konsequenzen.

Eine davon ist, dass wir keinen Kompromiss zwischen Exploration und Exploitation implementieren müssen. Eine stochastische Richtlinie ermöglicht es unserem Agenten, den Zustandsraum zu erkunden, ohne immer die gleichen Maßnahmen zu ergreifen. Dies liegt daran, dass eine Wahrscheinlichkeitsverteilung über Aktionen ausgegeben wird. Infolgedessen wird der Kompromiss zwischen Exploration und Exploitation ohne harte Codierung abgewickelt.

We also get rid of the problem of perceptual aliasing. Perceptual aliasing is when we have two states that seem to be (or actually are) the same, but need different actions.

Let’s take an example. We have a intelligent vacuum cleaner, and its goal is to suck the dust and avoid killing the hamsters.

Our vacuum cleaner can only perceive where the walls are.

The problem: the two red cases are aliased states, because the agent perceives an upper and lower wall for each two.

Under a deterministic policy, the policy will be either moving right when in red state or moving left. Either case will cause our agent to get stuck and never suck the dust.

Under a value-based RL algorithm, we learn a quasi-deterministic policy (“epsilon greedy strategy”). As a consequence, our agent can spend a lot of time before finding the dust.

On the other hand, an optimal stochastic policy will randomly move left or right in grey states. As a consequence it will not be stuck and will reach the goal state with high probability.

Disadvantages

Naturally, Policy gradients have one big disadvantage. A lot of the time, they converge on a local maximum rather than on the global optimum.

Instead of Deep Q-Learning, which always tries to reach the maximum, policy gradients converge slower, step by step. They can take longer to train.

However, we’ll see there are solutions to this problem.

Policy Search

We have our policy π that has a parameter θ. This π outputs a probability distribution of actions.

Awesome! But how do we know if our policy is good?

Remember that policy can be seen as an optimization problem. We must find the best parameters (θ) to maximize a score function, J(θ).

There are two steps:

  • Measure the quality of a π (policy) with a policy score function J(θ)
  • Use policy gradient ascent to find the best parameter θ that improves our π.

The main idea here is that J(θ) will tell us how good our π is. Policy gradient ascent will help us to find the best policy parameters to maximize the sample of good actions.

First Step: the Policy Score function J(θ)

To measure how good our policy is, we use a function called the objective function (or Policy Score Function) that calculates the expected reward of policy.

Three methods work equally well for optimizing policies. The choice depends only on the environment and the objectives you have.

First, in an episodic environment, we can use the start value. Calculate the mean of the return from the first time step (G1). This is the cumulative discounted reward for the entire episode.

The idea is simple. If I always start in some state s1, what’s the total reward I’ll get from that start state until the end?

We want to find the policy that maximizes G1, because it will be the optimal policy. This is due to the reward hypothesis explained in the first article.

For instance, in Breakout, I play a new game, but I lost the ball after 20 bricks destroyed (end of the game). New episodes always begin at the same state.

I calculate the score using J1(θ). Hitting 20 bricks is good, but I want to improve the score. To do that, I’ll need to improve the probability distributions of my actions by tuning the parameters. This happens in step 2.

In a continuous environment, we can use the average value, because we can’t rely on a specific start state.

Each state value is now weighted (because some happen more than others) by the probability of the occurrence of the respected state.

Third, we can use the average reward per time step. The idea here is that we want to get the most reward per time step.

Second step: Policy gradient ascent

We have a Policy score function that tells us how good our policy is. Now, we want to find a parameter θ that maximizes this score function. Maximizing the score function means finding the optimal policy.

To maximize the score function J(θ), we need to do gradient ascent on policy parameters.

Gradient ascent is the inverse of gradient descent. Remember that gradient always points to the steepest change.

In gradient descent, we take the direction of the steepest decrease in the function. In gradient ascent we take the direction of the steepest increase of the function.

Why gradient ascent and not gradient descent? Because we use gradient descent when we have an error function that we want to minimize.

But, the score function is not an error function! It’s a score function, and because we want to maximize the score, we need gradient ascent.

The idea is to find the gradient to the current policy π that updates the parameters in the direction of the greatest increase, and iterate.

Okay, now let’s implement that mathematically. This part is a bit hard, but it’s fundamental to understand how we arrive at our gradient formula.

We want to find the best parameters θ*, that maximize the score:

Our score function can be defined as:

Which is the total summation of expected reward given policy.

Now, because we want to do gradient ascent, we need to differentiate our score function J(θ).

Our score function J(θ) can be also defined as:

We wrote the function in this way to show the problem we face here.

We know that policy parameters change how actions are chosen, and as a consequence, what rewards we get and which states we will see and how often.

So, it can be challenging to find the changes of policy in a way that ensures improvement. This is because the performance depends on action selections and the distribution of states in which those selections are made.

Both of these are affected by policy parameters. The effect of policy parameters on the actions is simple to find, but how do we find the effect of policy on the state distribution? The function of the environment is unknown.

As a consequence, we face a problem: how do we estimate the ∇ (gradient) with respect to policy θ, when the gradient depends on the unknown effect of policy changes on the state distribution?

The solution will be to use the Policy Gradient Theorem. This provides an analytic expression for the gradient ∇ of J(θ) (performance) with respect to policy θ that does not involve the differentiation of the state distribution.

So let’s calculate:

Remember, we’re in a situation of stochastic policy. This means that our policy outputs a probability distribution π(τ ; θ). It outputs the probability of taking these series of steps (s0, a0, r0…), given our current parameters θ.

But, differentiating a probability function is hard, unless we can transform it into a logarithm. This makes it much simpler to differentiate.

Here we’ll use the likelihood ratio trick that replaces the resulting fraction into log probability.

Now let’s convert the summation back to an expectation:

As you can see, we only need to compute the derivative of the log policy function.

Now that we’ve done that, and it was a lot, we can conclude about policy gradients:

This Policy gradient is telling us how we should shift the policy distribution through changing parameters θ if we want to achieve an higher score.

R(tau) is like a scalar value score:

  • If R(tau) is high, it means that on average we took actions that lead to high rewards. We want to push the probabilities of the actions seen (increase the probability of taking these actions).
  • On the other hand, if R(tau) is low, we want to push down the probabilities of the actions seen.

This policy gradient causes the parameters to move most in the direction that favors actions that has the highest return.

Monte Carlo Policy Gradients

In our notebook, we’ll use this approach to design the policy gradient algorithm. We use Monte Carlo because our tasks can be divided into episodes.

Initialize θfor each episode τ = S0, A0, R1, S1, …, ST: for t <-- 1 to T-1: Δθ = α ∇theta(log π(St, At, θ)) Gt θ = θ + Δθ
For each episode: At each time step within that episode: Compute the log probabilities produced by our policy function. Multiply it by the score function. Update the weights

But we face a problem with this algorithm. Because we only calculate R at the end of the episode, we average all actions. Even if some of the actions taken were very bad, if our score is quite high, we will average all the actions as good.

So to have a correct policy, we need a lot of samples… which results in slow learning.

How to improve our Model?

We’ll see in the next articles some improvements:

  • Actor Critic: a hybrid between value-based algorithms and policy-based algorithms.
  • Proximale Richtlinienverläufe: Stellt sicher, dass die Abweichung von der vorherigen Richtlinie relativ gering bleibt.

Lassen Sie es uns mit Cartpole und Doom implementieren

Wir haben ein Video gemacht, in dem wir einen Policy Gradient-Agenten mit Tensorflow implementieren, der lernt, Doom zu spielen? in einer Deathmatch-Umgebung.

Sie können direkt auf die Notizbücher im Repo des Deep Reinforcement Learning Course zugreifen.

Cartpole:

Untergang:

Das ist alles! Sie haben gerade einen Agenten erstellt, der lernt, in einer Doom-Umgebung zu überleben. Genial!

Vergessen Sie nicht, jeden Teil des Codes selbst zu implementieren. Es ist wirklich wichtig zu versuchen, den Code zu ändern, den ich Ihnen gegeben habe. Versuchen Sie, Epochen hinzuzufügen, die Architektur zu ändern, die Lernrate zu ändern, eine härtere Umgebung zu verwenden ... und so weiter. Habe Spaß!

Im nächsten Artikel werde ich die letzten Verbesserungen in Deep Q-Learning diskutieren:

  • Feste Q-Werte
  • Priorisierte Erfahrungswiedergabe
  • Doppelter DQN
  • Dueling Networks

If you liked my article, please click the ? below as many time as you liked the article so other people will see this here on Medium. And don’t forget to follow me!

If you have any thoughts, comments, questions, feel free to comment below or send me an email: [email protected], or tweet me @ThomasSimonini.

Keep Learning, Stay awesome!

Deep Reinforcement Learning Course with Tensorflow ?️

? Syllabus

? Video version

Part 1: An introduction to Reinforcement Learning

Part 2: Diving deeper into Reinforcement Learning with Q-Learning

Part 3: An introduction to Deep Q-Learning: let’s play Doom

Part 3+: Improvements in Deep Q Learning: Dueling Double DQN, Prioritized Experience Replay, and fixed Q-targets

Part 4: An introduction to Policy Gradients with Doom and Cartpole

Part 5: An intro to Advantage Actor Critic methods: let’s play Sonic the Hedgehog!

Part 6: Proximal Policy Optimization (PPO) with Sonic the Hedgehog 2 and 3

Part 7: Curiosity-Driven Learning made easy Part I