Python Grammar
Python
1D = collections.defaultdict(list)
创建一个默认映射到list的字典。(帮助避免了很多意外情况)
12op,l,r,y,z = map(int,input().split())t = ''.join(input().split(" "))
很方便的处理一行的输出,split()默认跳过空白字符。
将输入拼成一个字符串,方便处理。
1a.sort(key=lambda x:x.r)
对a本生进行排序,这里有key函数:按照key=(比较函数),进行比较。比较函数,可以很方便的用lambda来表示。
如果想反过来排序,可以用reverse=True参数。
1print("{0} - > {1}".format(i.l,i.r),end="\n")
格式化输出,这里的0和1是format函数的参数,可以用来指定输出的位置。同时python print自带换行,如果不想换行可以自定义end参数 ...
PPO code experiment
PPO code experiment
detect0530@gmail.com
This is a simple experiment to test the PPO algorithm on the OpenAI gym environment.
All code resource is from the repository: Link1, which is also inspired by a blog paper from 37 PPO Tricks.
Here, I’d like to split the code frame, and note what I have learned from the code.
Code Frame
main
argparse, set the hyperparameter
tensorboard, log the training process
evaluate policy, test the policy
train policy, train the policy
ppo_agent
Actor Mod ...
Proximal Policy Optimization(PPO)
Proximal Policy Optimization(PPO)
detect0530@gmail.com
Background: PG and TRPO
Policy Gradient
我们使用策略网络进行决策,对于每一版的policy network,我们使用on-policy的方法获得数据,并使用这些数据更新网络,得到下一版的policy network。
更新过程其实就是根据Reward来调整给每一个action分配的权重。
Tips:
增加一个基线
原始算法我们用reward的大小作为引导,但是reward设计的不好时,由于采取动作都会有奖励,一是有noise,二是这样引导会错过一些未访问过的good action。于是我们引入基线(一般设置为V(s),表示所有采样序列的平均奖励),高于基线,给正奖励;低于基线,给负奖励。
折扣因子
降低未来reward的权重,只需要对奖励序列的求和计算增加一个gamma因子即可。
优势函数
回顾之前的算法,对于一个采样序列中的数据点,我们都是用相同的R(γ)R(\gamma)R(γ)作为系数,这样很粗糙。实际上好 ...
DDPG
Deep Deterministic Policy Gradient
Background
在过去的DQN实践中,我们更多的采用神经网络直接对状态s进行近似,映射分数到动作空间里然后再根据得分选择动作。这种方法在离散动作空间中表现良好,但是在连续动作空间中表现不佳。因为在连续动作空间中,动作空间的维度很高,而且动作空间的连续性使得我们无法直接使用神经网络来近似动作空间。因此,我们需要一种新的方法来解决这个问题。
Quick Facts
DDPG is an off-policy algorithm.
DDPG can only be used for environments with continuous action spaces.
DDPG can be thought of as being deep Q-learning for continuous action spaces.
Key Equations
我们从两个角度理解DDSG,一个是Q-learning的角度,另一个是策略梯度的角度。
Q-learning角度
L(ϕ,D)=E(s,a,r,s′,d)∼P[( ...
Dueling-DQN
Dueling DQN
Abstract
我们评估两个东西,一个是状态价值,一个是动作优势函数。在动作价值接近的时候,会很work。
为什么要采用对偶网络结构?
其实动机很简单:很多游戏的Q值,只受当前状态影响,无论采取什么动作区别不大。如下图所示:
这是Atari game中的一个赛车游戏,Value表示状态价值,Advantage表示动作优势值,图中黄色部分表示注意力。当前方没有车辆时,智能体左右移动并没有影响,说明动作对Q值没有影响,但是状态对Q值很有影响。从上面两幅图可以看出,Value更加关注远方道路,因为开的越远,对应的状态值越大;Advantage没有特别注意的地方,说明动作没有影响。当前方存在车辆阻挡时,智能体的动作选择至关重要,说明动作对Q值存在影响,同样状态对Q值也会存在影响。从下面两幅图可以看出,Value同样更加关注远方道路,但是Advantge此时会关注前方车辆,因为如果不采取相应动作,智能体很有可能会发生碰撞,分数就会很低。对偶网络思想符合很多场景的设定。
可以看到,状态函数和价值函数关注的是不一样的东西。
定义优势函数:
Aπ=Qπ(s,a)−V ...
Prioritized Experience Replay
Prioritized Experience Replay
Experience replay的演化
online RL:缺点:经验之间是correlated的,不满足stochastic gradient-decent的要求。另外,有用的好经验被使用一次后就遗忘了。
普通的experience replay可以记下经验,然后抽样更新参数,这样一方面减少了对打量经验的需求,转而用更多的计算力和内存(经常比RL agent和环境交互更cheaper)
而Prioritized experience replay further liberates the agents from considering transitions with the same frequency that they are experienced.
一些tricks
总的来说,用TD error来衡量经验的重要性,但是这样有两个问题:
(a) loss of diversity,影响stochastic gradient descent的性能。
(b) introduce bias,需要我们用impor ...
DDQN
Double DQN
DQN的overestimation的问题
众所周知DQN有substantial overestimations的问题
乐观估计在某种程度上是我们鼓励在不确定时的探索技巧,但是因为DQN中max操作和各种噪音、误差的原因,这种乐观估计不是uniform或者集中在我们希望的status上,会造成性能退化。
Atari游戏很适合DQN,因为环境是deterministic,同时deep nn可以很好地渐进拟合Q值。
我们依然用原nn评估用哪一个动作,但是计算这个动作的最后TD估计时,我们用另一个nn来计算。这样可以减少overestimation的问题。
errors and noises
errors and noises无处不在,包括environment,function approximation,non-stationary,这是很显然的,因为我们不知道true values,任何的方法都有不准确性。即是没有bias,uniform是0,也会有variance。这些都会导致overestimation。
数学上bias和variance导致的o ...
DS作业汇报 Fibonacci堆
DS作业汇报 Fibonacci堆
detect0530@gmail.com
探究Fibonacci堆对dijkstra算法的优化效果
复杂度分析,与常见堆结构的理论横向对比
实现Fibonacci堆
验证Fibonacci堆的正确性
利用qt实现可视化效果,方便调试
设定check函数,自动检测堆性质以及双向链表的正确性
与其他堆以及stl提供的priority_queue进行对拍比较
将正确性得到保证的Fibonacci堆应用到dijkstra算法中,并在随机&高压数据集上进行测试,并记录实验结构
分析实验结果,得出结论
理论复杂度对比
操作 \ 数据结构
配对堆
二叉堆
左偏树
二项堆
斐波那契堆
插入(insert)
O(1)O(1)O(1)
O(logn)O(\log n)O(logn)
O(logn)O(\log n)O(logn)
O(logn)O(\log n)O(logn)
O(1)O(1)O(1)
查询最小值(find-min)
O(1)O(1)O(1)
O(1)O(1)O(1)
O(1)O(1)O(1)
O(1)O ...
DQN coding exercise
DQN theory and practice
detect0530@gmail.com
以下是DQN完成atari游戏Pong的代码实现,包括了完整的朴素DQN实现,以及experience replay和target network的改进。代码实现基于PyTorch和OpenAI Gym。
并使用Chatgpt生成相应的代码注释,以及各个package api的介绍。
123USE_CUDA = torch.cuda.is_available()dtype = torch.cuda.FloatTensor if torch.cuda.is_available() else torch.FloatTensorVariable = lambda *args, **kwargs: autograd.Variable(*args, **kwargs).cuda() if USE_CUDA else autograd.Variable(*args, **kwargs)
这段代码主要是用于检查是否可用CUDA(用于GPU加速),然后根据可用性设置相应的数据类型和变量。
USE_C ...