时间差分学习（Temporal Difference Learing）
预测，估计值函数；控制，优化值函数。
离线：Q学习；在线：SARSA。
智能体驾驶出租车。 总共有四个地点，智能体必须在一个地方接载一名乘客，然后在另一个地方放下乘客。 智能体将获得 20分作为成功下车的奖励，并且每次获得的时间步数为-1分。 非法接送和丢弃的智能体也将失去-10分。 因此，智能体的目标是学习在短时间内在正确的位置接载和放下乘客，无需登上任何非法乘客。
出租车案例-Q学习
代码语言：javascript复制import random
import gym
env = gym.make('Taxi-v2')
env.render()
q = {}
for s in range(env.observation_space.n):
for a in range(env.action_space.n):
q[(s,a)] = 0.0
def update_q_table(prev_state, action, reward, nextstate, alpha, gamma):
qa = max([q[(nextstate, a)] for a in range(env.action_space.n)])
q[(prev_state,action)] = alpha * (reward gamma * qa - q[(prev_state,action)])
def epsilon_greedy_policy(state, epsilon):
if random.uniform(0,1) < epsilon:
return env.action_space.sample()
else:
return max(list(range(env.action_space.n)), key = lambda x: q[(state,x)])
alpha = 0.4
gamma = 0.999
epsilon = 0.017
for i in range(8000):
r = 0
prev_state = env.reset()
while True:
env.render()
# In each state, we select the action by epsilon-greedy policy
action = epsilon_greedy_policy(prev_state, epsilon)
# then we perform the action and move to the next state, and receive the reward
nextstate, reward, done, _ = env.step(action)
# Next we update the Q value using our update_q_table function
# which updates the Q value by Q learning update rule
update_q_table(prev_state, action, reward, nextstate, alpha, gamma)
# Finally we update the previous state as next state
prev_state = nextstate
# Store all the rewards obtained
r = reward
#we will break the loop, if we are at the terminal state of the episode
if done:
break
print("total reward: ", r)
env.close()部分结果如下：
代码语言：javascript复制 ---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : |_: |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : :_: |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : :_: : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : :_: : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| :_: : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R:_| : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
total reward: 7出租车案例-SARSA
代码语言：javascript复制import random
import gym
env = gym.make('Taxi-v2')
env.render()
Q = {}
for s in range(env.observation_space.n):
for a in range(env.action_space.n):
Q[(s,a)] = 0.0
def epsilon_greedy(state, epsilon):
if random.uniform(0,1) < epsilon:
return env.action_space.sample()
else:
return max(list(range(env.action_space.n)), key = lambda x: Q[(state,x)])
alpha = 0.85
gamma = 0.90
epsilon = 0.8
for i in range(4000):
# we store cumulative reward of each episodes in r
r = 0
# initialize the state,
state = env.reset()
# select the action using epsilon-greedy policy
action = epsilon_greedy(state,epsilon)
while True:
# env.render()
env.render()
# then we perform the action and move to the next state, and receive the reward
nextstate, reward, done, _ = env.step(action)
# again, we select the next action using epsilon greedy policy
nextaction = epsilon_greedy(nextstate,epsilon)
# we calculate the Q value of previous state using our update rule
Q[(state,action)] = alpha * (reward gamma * Q[(nextstate,nextaction)]-Q[(state,action)])
# finally we update our state and action with next action and next state
action = nextaction
state = nextstate
# store the rewards
r = reward
# we will break the loop, if we are at the terminal state of the episode
if done:
break
print("total reward: ", r)
env.close()部分结果显示如下：
代码语言：javascript复制 ---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Dropoff)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(North)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(South)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(Pickup)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(East)
---------
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
---------
(West)
total reward: -695参考文献资料：
- https://github.com/shashir/td-learning
- https://link.springer.com/article/10.1007/BF00115009
- https://link.springer.com/content/pdf/10.1007/BF00115009.pdf
Temporal difference (TD) learning (Sutton, 1988; Barto et al., 1990; Bertekas and Tsitsiklis, 1996; Sutton and Barto, 1998) is a form of error-driven learning used in feed-forward neural networks in which input patterns(e.g., patterns of place cell activity) are to be associated with output values(e.g., an expectation of how close the goal is), but where additionally there isinformation to be had in the sequence in which input patterns and outputvalues present themselves.
