detect

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(γ)作为系数，这样很粗糙。实际上好 ...

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 Abstract 我们评估两个东西，一个是状态价值，一个是动作优势函数。在动作价值接近的时候，会很work。 为什么要采用对偶网络结构？ 其实动机很简单：很多游戏的Q值，只受当前状态影响，无论采取什么动作区别不大。如下图所示： 这是Atari game中的一个赛车游戏，Value表示状态价值，Advantage表示动作优势值，图中黄色部分表示注意力。当前方没有车辆时，智能体左右移动并没有影响，说明动作对Q值没有影响，但是状态对Q值很有影响。从上面两幅图可以看出，Value更加关注远方道路，因为开的越远，对应的状态值越大；Advantage没有特别注意的地方，说明动作没有影响。当前方存在车辆阻挡时，智能体的动作选择至关重要，说明动作对Q值存在影响，同样状态对Q值也会存在影响。从下面两幅图可以看出，Value同样更加关注远方道路，但是Advantge此时会关注前方车辆，因为如果不采取相应动作，智能体很有可能会发生碰撞，分数就会很低。对偶网络思想符合很多场景的设定。 可以看到，状态函数和价值函数关注的是不一样的东西。 定义优势函数： Aπ=Qπ(s,a)−V ...

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 ...

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堆 detect0530@gmail.com 探究Fibonacci堆对dijkstra算法的优化效果 复杂度分析，与常见堆结构的理论横向对比 实现Fibonacci堆 验证Fibonacci堆的正确性 利用qt实现可视化效果，方便调试 设定check函数，自动检测堆性质以及双向链表的正确性 与其他堆以及stl提供的priority_queue进行对拍比较 将正确性得到保证的Fibonacci堆应用到dijkstra算法中，并在随机&高压数据集上进行测试，并记录实验结构 分析实验结果，得出结论 理论复杂度对比 操作 \ 数据结构 配对堆 二叉堆 左偏树 二项堆 斐波那契堆 插入（insert） O(1)O(1)O(1) O(log⁡n)O(\log n)O(logn) O(log⁡n)O(\log n)O(logn) O(log⁡n)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 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 ...

DQN theory and practice detect0503@gmail.com original paper: Playing Atari with Deep Reinforcement Learning Abstract This is a simple experiment to train a DQN agent to play atari game Pong. This paper proposes a novel approach, directly using the entire game screen as input for the model. The model autonomously determines what features to extract, and even the specific features it learns are not of primary concern. What matters is that the model can make correct actions in various states, ...

Macro placement by black-box optimization detect0530@gmail.com 1 问题分析 通过阅读发下来的code，发现需要我调整的黑箱问题是，给定一组长度为dim，有上下界的整数序列。 实例代码使用随机搜索的方法，通过不断生成随机数列来更新最优答案。 由于BBO已经为我们设计好了评价黑盒，我们只需要考虑如何在这组数列上进行演化算法即可。 2 基本的演化算法设计 & 比较不同mutation,crossover的性能 2.1 种群设置 由于单次黑盒评估运算量巨大（2-5s），我们需要尽可能减少黑盒评估次数。 所以种群大小一开始定为10 2.2 selection 初始算法中，我将随机从种群中选出父代。 2.3 mutaion 随机选择两个位置进行位置交换 以概率p1对每个位置进行随机变化 2.4 crossover 选出两个父代后： 随机选择断点，然后将两个父代的断点两侧进行交换 以概率p2对每个位置进行父代交换 survival selection 以n+n策略进行精英保留，保存最优的n个个体 设计好基本的演 ...

《深度强化学习》reading notes detect0530@gmail.com 价值学习 Optimal Bellman Equation On-Policy and Off-policy 按照交互中的策略与最终的策略是否一致，可以分为两类：On-Policy和Off-Policy。 SARSA Algorithm 可以说和Q学习基本类似，但是SARSA是On-Policy，而Q学习是Off-Policy。因为在每一次选择action时都是基于当前的策略函数π\piπ来选择的(而不是Q学习中ϵ−greedy\epsilon-greedyϵ−greedy抽样和最优action选择)。 同时引入多步TD的做法，指应用πnow\pi_{now}πnow​连续交互m次，然后再用梯度优化，因为真实数据由一步变成了多步，更稳定效果更好。 训练流程中走n步，对前n-m步都可以用来更新梯度，最后sigma求和梯度即可。 由此看来多步TD是比较抽象化的做法，当步数确定为极端情况时，实际上有之前讨论过的含义： 补充一点上图中提到的相关概念： 由此可见，多步TD算法如果步数 ...