【强化学习笔记】Reinforcement Learning Notes.pdf

Reinforcement Learning

An Introductory Note

Jingye Wang

Ó wangjy5@shanghaitech.edu.cn

Spring 2020

Contents

1 Introduction 3

2 Review of Basic Probability 5

2.1 Interpretation of Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Bandit Algorithms 14

3.1 Bandit Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2 Stochastic Bandits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.3 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.4 UCB Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.5 ompson Sampling Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.6 Gradient Bandit Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4 Markov Chains 20

4.1 Markov Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.2 Basic Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.1 Markov Reward Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

5.2 Markov Decision Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5.3 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

6 Model-Free Prediction 33

6.1 Monte-Carlo Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6.2 Temporal-Dierence Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

7 Model-Free Control 37

7.1 On Policy Monte-Carlo Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

7.2 On Policy Temporal-Dierence Control: Sarsa . . . . . . . . . . . . . . . . . . . . . . . . 39

7.3 O-Policy Temporal-Dierence Control: Q-Learning . . . . . . . . . . . . . . . . . . . . 40

9.3 Actor-Critic Policy Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

9.4 Extension of Policy Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

1 Introduction

Course Prerequisite:

• Linear Algebra

• Probability

• Machine Learning relevant course (data mining, pattern recognition, etc)

• PyTorch, Python

What is Reinforcement Learning and why we care:

a computational approach to learning whereby an agent tries to maximize the total amount of reward

• ere is

Big deal: Able to Achieve Superhuman Performance

• Upper bound for Supervised Learning is human-performance.

• Upper bound for Reinforcement Learning ?

Why Reinforcement Learning works now?

• Computation power: many GPUs to do trial-and-error rollout;

• Acquire the high degree of prociency in domains governed by simple, known rules;

• End-to-end training, features and policy are jointly optimized toward the end goal.

Sequential Decision Making:

• Full observability: agent directly observes the environment state, formally as Markov decision process

(MDP);

Types of Reinforcement Learning Agents based on What the Agent Learns

• Value-based agent:

• Policy-based agent:

• Actor-Critic agent:

2 Review of Basic Probability

For more details of this part one can refer to Introduction to Probability [2] and Monte Carlo Statistical

Methods [3].

e Frequentist view: Probability represents a long-run frequency over a large number of repetitions of

an experiment.

e Bayesian view: Probability represents a degree of belief about the event in question.

Many machine learning techniques are derived from these two views. As the computing power and

algorithms develop, however, Bayesian is becoming dominant.

matrix

···

n

.

.

.

.

.

.

.

.

.

.

.

.

Strong Law of Large Numbers (SLLN): e sample mean

X

as n → ∞, w.p.1(i.e. with probability 1). In other words, the event

X