我是这样度过每一天
----向死而生-----
折返点1603 改变，朝着跑者的方向
我想，跑步可能是人类最为自然的一种体育锻炼形式了吧。即便如此，人类也需要花上接近两年的时间，才能比较灵活的跑起来。我们先学会爬，然后在一岁前后，...
-
折返点1602：为什么喜欢跑步
喜欢跑步，不知为什么。 第一次长跑的记忆，在我的脑海中很清晰。那是从小学时候的一次体育课。那次课上，体育老师准许我们离开操场，在路上奔跑。 不记...
-
折返点1601：跑步是有害的
提到人的寿命，人们习惯成自然的用年岁来记录。比如中国人的人均期望寿命，目前是74岁左右。还有好事者将年换算成月、周、天。同样的生命长度，在不同的...
-
我的新年夜，应该写点儿什么
我们居住的是个球——虽不是完美的球形，但是地“球”的说法是连信上帝的人也都认可了的。其实认真追究起来，也没有多少人亲见地球的样子。大家都是通过科...
-
2015的学习、阅读与书写
奥巴马做完了他的年度总结，去度假了。 这是我的。 OMSCS OMSCS 全称是 Online Master of Science in Com...
-
天生牛奶血
引子：身边的变种人 现代人熟悉变种人（mutant），是通过各种动漫作品、影视节目。《X战警》系列，《Heroes》，《神奇四侠》，《蜘蛛侠》等...
-
8803 RL Fall 2015 期末复习笔记精简版
简介： 这是在复习Reinforcement Learning的期末考的时候做的复习笔记。基本内容就是平时的课堂笔记（参见2015秋季学期笔记 ...
-
2015秋季学期笔记 8803 RL and 6440 HIT
Reinforcement Learning 课程笔记 Reinforcement Learning 第一周课程笔记 : MDP Reinfor...
-
Solving Five-step Random-Walk problem with TD(λ) | Fall-2015 CS8803 RL
Reinforcement Learning (CS8803-O03) Nov. 29, 2015Solving Five-step Random-Walk problem with TD(λ)
TD-Lambda (TD(λ)), a machine learning algorithm designed for reinforcement learning problems, is invented by Richard S. Sutton(Sutton, 1988). Sutton performed two computational experiments on a 5-step random-walk problem to demonstrate the performance of TD(λ). This report is to replicate the experiments using the exact method described in Sutton’s paper.
The 5-step random-walk example consists of a Markov chain of 5 lined up states (B, C, D, E, and F) which are bounded by two extra absorbing states (A and G, Figure 1). For the non-absorbing states, the transition probabilities of moving to the right and to the right are both 0.5, and the ideal probability of a walk ending in state G from each state is: T = {1/6 2/6 3/6 4/6 5/6}, (e.g. p(G B) = 1/6). The reward for states A and G are 0 and 1, respectively. The goal is to learn the estimated transition probabilities (a weight vector w) over a series of random-walks using the TD method. 
Method
To evaluate the performance of TD(λ) method, 100 training sets, each consists of 10 random-walk sequences, were generated. The root mean squared (RMS) error of w against the ideal predictions T were calculated and averaged across the 100 training sets.
In experiment 1 (repeated presentation), each training set was fed to the learning algorithm repeatedly until converge. w will be updated only after the algorithm was trained on the 10 sequences in a training set. Sutton mentioned that TD(λ) will always converge when learning rate is small, but the learning rate or the convergence threshold were not reported. In this replication effort, learning rate (α) and convergence threshold (ε) were was to 0.05 and 0.0005, respectively. Smaller ε was tried but the implementation would get numerical overflow before converge.
In experiment 2, the algorithm will see the training sets only once update w after each sequence. To demonstrate the effect of learning rate (α) on the performance of TD(λ), multiple learning rate were applied to the learning algorithm.
Results
The main findings replicated Sutton’s original paper. In the repeated presentation experiment, the performance of TD(λ) declines as λ increases and TD(0) has the best performance. The error increases rapidly as λ approaching to 1 (Figure 2) with TD(1) has the worst performance. As shown in figure 3, the value of learning rate has evident effects on the performance of TD(λ) and most of the TD(λ) performed the best when α = 0.2 (the best α in Sutton’s original paper is 0.3). Figure 4 shows the best RMS error level of for each λ in TD(λ) when the best α is applied to the corresponding λ. In this case, TD(0) does not have the best performance any more, and TD(0.2) seems to have the best performance.
Discussion
This replication supports Sutton’s claims, but the results were not exactly the same as what’s in the original paper. For example, the range of RMS errors for experiment 1 was [.10 .17], the best α and best performer in experiment 2 were around 0.2 and TD(0.2), but in the original paper, they were [.19 .25], α = 0.3 and TD(0.3). This is not surprising for two reasons. A). Some parameters (α and ε) were not reported in the original paper; B). The training sets were randomly generated. α and ε can affect the converging process and the distribution of random-walk sequences will affect the learning results.
In conclusion, the replication supports the claims of the original paper.
Reference
Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine learning, 3(1), 9-44.
-
Reinforcement Learning 第十四周课程笔记
This week should watch CCC. The readings are: Zeibart et al. (2008). Bab...