Let's read: Sutton's RL, week 5 to 6, chap 6

In this post we read chapter 6, about Temmporal Difference (TD) learning:

If one had to identify one idea as central and novel to reinforcement learning, it would undoubtedly be TD learning... The relationship between TD, DP, and MC methods is a recurring theme in RL.

TD learning is a combination of MC and DP.

• Like MC, TD methods can learn directly from raw experience without a model of the environment’s dynamics.
• Like DP, TD methods update estimates based in part on other learned estimates, without waiting for a final outcome (they bootstrap).
• Bootstrapping: using a guess to make a better guess.
• The master of RL must master TD, MC, DP as one and use them in many combinations.

Let's read: Sutton's RL, week 4 to 5, chap 5

In this post we do chapter 5. Finally, we are going into Monte Carlo methods!! Almost enough to understand AlphaGo!

MC methods in this chapter differ from the DP methods in two major ways. First, they operate on sample experience, and thus can be used for direct learning without a model. Second, they do not bootstrap. That is, they do not update their value estimates on the basis of other value estimates. 

These two differences are not tightly linked, and can be separated. In the next chapter we consider methods that learn from experience, like Monte Carlo methods, but also bootstrap, like DP methods.

Let's read: Sutton's RL, week 3, 4, chap 4

We'll first finish chapter 4.1 from week 3, and for week 4, we'll do:

• Sutton & Barto, rest of Chapter 4
• Sutton & Barto, Chapter 5

In this post we do chapter 4.

Dynamic Programming (DP)

Define: DP: a collection of algorithms to compute optimal policies for an MDP model of the environment. 

Classical DP algorithms are of limited utility in reinforcement learning both because of their assumption of a perfect model and because of their great computational expense, but they are still important theoretically. DP provides an essential foundation for the understanding of the methods presented in the rest of this book. In fact, all of these methods can be viewed as attempts to achieve much the same effect as DP, only with less computation and without assuming a perfect model of the environment.

Basically, can't solve Bellman, can't do classical DP, put them up as unachievable ideals and opt for more practical algorithms that can approximate them.

Let's read: Sutton's RL, week 3, chap 3

For week 3, we will do:

• Rest of Sutton & Barto Chapter 3
• Sutton & Barto Summary of Notation, 
• Sutton & Barto Section 4.1 

Optimal Policy

Define: given a MDP problem, we have a corresponding policy spaces $\Pi$ of all possible policies for the problem. $\Pi$ is preordered by Pareto ordering:

\[\pi_1 \succeq \pi_2 \quad \text{iff} \quad \forall s\in S, v_{\pi_1}(s) \ge v_{\pi_2}(s)\]

That is, a policy is better than another iff using it does not deprove the expected value in all situations, and improves in at least one.

A policy $\pi$ is optimal iff it is a maximal element in $\Pi$ thus preordered.

The optimal state-value function is defined as as the best that can be done by any policy at a certain state, it's a bit subtler than that

 \[v_*(s) = \max_\pi v_\pi(s)\]

and similarly for $q_*$

Let's read: Sutton's RL, week 2, chap 3

For week 2, we will do:

• Read the definition given for artificial intelligence in Wikipedia and in the Nilsson book on p13; 
• google for and read “John McCarthy basic questions”, “the intentional stance (dictionary of philosophy of mind)”
• Sutton & Barto Chapter 3 to Section 3.5

Reading

From Wikipedia: 

intelligence demonstrated by machines, ... "intelligent agents": any device that perceives its environment and takes actions that maximize its chance of successfully achieving its goals. Colloquially, ... a machine [that] mimics "cognitive" functions that humans associate with other human minds, such as "learning" and "problem solving".

From The Quest for Artificial Intelligence (2009), Nils Nilsson:

intelligence is that quality that enables an entity to function appropriately and with foresight in its environment... Because “functioning appropriately and with foresight” requires so many different capabilities, depending on the environment, we actually have several continua of intelligences with no particularly sharp discontinuities in any of them. For these reasons, I take a rather generous view of what constitutes AI.

Let's read: Sutton's RL, week 1, chap 2

Chapter 2

This chapter is about multiarmed bandits (MAB). 

There are two kinds of feedbacks to a RL agent:

Evaluative feedback: how well did it act (a score).

Instructive feedback: best action it could do (a correct answer)

In MAP, the environment is a Markov chain, and thus the past does not influence the future. This makes it easy. 

This is called nonassociative learning.

In general,

\[Q_t(a) \approx q_*(a) = \mathbb{E}(R_t | A_t = a)\]

$Q_t(a)$ is the estimate of $q_*(a)$, estimated at time $t$. It is updated as time goes on, hopefully approaching $q_*(a)$ better and better.

The greedy strategy is 

\[A_t = \underset{a}{\operatorname{argmax}}Q_t(a)\]

The key is to estimate $Q_t$ accurately. There are several ways.

Let's read: Sutton's RL, week 1, chap 1

This is the first post in a series of posts as I read through Richard Sutton's Reinforcement Learning: An Introduction (2nd edition, 2018), which is freely available on Sutton's site, thanks to his philosophy of GNU.

We will follow the textbook and do some assignments as seen from the folder, following the course schedule. The course schedule gives it as a 10 week course though we won't go through them all.

And a warning: I wrote this as review, so you'd better read the book yourself, since I will only write the bare minimum needed and not give more explanations. I will also post my exercise solutions.

Week 1 tasks

• Section 1 of the Wikipedia entry for “the technological singularity”; see also Species of Mind (2010), Vernor Vinge, and When will computer hardware match the human brain? (1998), Hans Moravec. 
• Sutton & Barto Chapters 1 and 2.
• Read probabilities-expectations.pdf in the dropbox.