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: Norvig's AI, chap 24, 25, 26, 27

Continuing from last post.

Chapter 24: Perception

This chapter is about feelings, or how to sense the world through sensors. It's too engineering for me so I skipped it.

Chapter 25: Robotics

This chapter is about robotics, actuators, or how to actually move around in the world. This is about the most traditional and engineering part of the textbook, and quite out of my part, so I'll skim it as much as I skimmed technical stuff in mechanical engineering during my study of Newtonian physics.

My favorite part from the chapter is a game:

Exercise 25.11: pretend to be a robot! A game for people from kindergarten to PhD! 

I can think of a few variations on this game: First, to make communication strictly minimal, players should only communicate through text messages and webcams. Second, instead of one person playing the brain, why not use two? One for each hemisphere! The left brain can only see the right eye and control the right hand, and vice versa. Then there will be six players. 

And we can even imagine a game of epiphenomenon.

Wait a minute, this sounds just like specialization...

Let's read: Norvig's AI, chap 22, 23

Continuing from last post.

Chapter 22-25 are about interactions with the environment:

• 22 is about reading and 
• 23 is about writing. 

Listening and speaking are not touched upon, but it's not a problem, considering that current technologies for speech-to-text and text-to-speech are pretty much perfect.

• 24 is about feeling (perception) and 
• 25 is about moving (robotics).

Let's read: Norvig's AI, chap 3

I'm tired of Norvig's AI now. It's too long. Much better if I can just refer to specific chapters of it when I need to get an introduction to a particular topic, rather than reading it in one go.
I will just post reading notes from what I've already accomplished.

---

Continuing from last post.

Chapter 3-6 are about solving given, well-defined problems by various kinds of searching. It is quite basic algorithmic stuff. There's no learning yet, and the agent can't improve itself.

Let's read: Norvig's AI, chap 2

Continuing from last post.

Chapter 2 overviews the idea of a rational agent: agents, environments, rationality, and some basic designs.

Agent

An agent in an environment receives percepts from sensors, and acts by actuators. Mathematically, we can model it as an agent function:
\[\text{Agent}: \{\text{Percept}\}^* \to \{\text{Action}\} \]

Let's read: Norvig's AI, chap 1

This is the first post in a series of posts as I read through Artificial Intelligence: A Modern Approach (3rd edition, 2009), by Peter Norvig, Stuart J. Russell. It's a behemoth with 1152 pages, eww. The book is unfortunately not free, but its pdf file is pretty easy to find online anyway, and most schools have a copy, too, just because it's so popular, as the official site says:

• The leading textbook in Artificial Intelligence. 
• Used in over 1300 universities in over 110 countries. 

We will study this book, not fully, it'd take about a year to do that! We'll just read as fast as possible to get the overview.

Today we read chapter 1.

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.