This chapter is dedicated to the important issue of
Markov decision processes, MDPs, are introduced as an extension
of Hidden Markov process where the actions
are chosen by the agent. Secondary rewards are important here too, in the sense that they provide the
feedback to rate the past actions as good or not. The problem is that frequently it is difficult to
assign rewards to each action. Actually, in some cases, the reward is only obtained after the completion
of the process. Thus the need to have bookkeeping mechanisms allowing the backpropagation of final
successes or failures. The difficult problem of handling such delayed rewards is the subject of
reinforcement learning, represented by Q-learning in Ballard's book.
Ballard starts his presentation of reinforcement learning by presenting some basic
notation and outlining two situations: maze following and pole balancing.
This is followed by a brief section
introducing the concept of value and the policy improvement concept. It is felt that the novice reader will
have substantial difficulties in following this section, because of some confusion and haste in the
presentation of the concepts. For instance, the state value functions in Figure 11.3 are not refered
to in the main text, which is restricted to discussing the value of policies. In addition, Q functions
are defined as the expected return of starting in state x, taking an specific action u, and then following
policy f thereafter. Actually, it should be observed that this latter policy is assumed optimal for the rest
of the transitions, in order to allow the dynamic programming principle to be extended to the problem. It
should be also observed that the definition of the reward estimation can strongly influence the determination
of the optimal policy. Unfortunately, the previous examples (maze and pole) are not retaken in the book,
leaving the reader wondering how they could be more formally approached in terms of reinforcement learning.
After a section discussing how the Q-functions can be obtained, Ballard proceeds to
present the interesting concept of temporal-difference learning, which is illustrated informally in terms of
the classical solution of Backgammon. The next
section introduces the approach of learning with a teacher,
covering the situations of learning with an external critic and learning by watching. The important issue of
partially observable MDPs is covered in terms of two strategies (avoiding bad states and learning state
information from temporal sequences) and illustrated in Section 11.7. This chapter concludes with a
summary outlining the most important covered issues.