detect

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算法如果步数 ...

浅析Alpha-Go detect0530@gmail.com 训练&执行步骤 先找很多对局素材，进行监督学习，然后分别训练policy和value network。 最后再依据policy和value函数进行蒙特卡洛树搜索。 Policy Network 通过191948的tensor表示状态，然后用convolutional layer提取特征，最后用softmax输出每个动作的概率。(361个动作) 一开始先用人的对局用来学习初步的策略网络。 用behavior cloning的方法（imitation learning 与reinforcement learning区别在于有无reword），让policy network去模仿人的对局。 其实就是一个交叉熵作为loss function的多分类问题。 Behavior cloning缺点是效果不好，没见过的话，不知道怎么走。 所以我们需要用reinforcement learning来改进behavior cloning训练出的policy network。 Train Policy network ...

DRL: Actor-Critic Method detect0530@gmail.com 基本概念 Discounted Return UtU_tUt​ 这个东西是一个随机变量，随机性由两部分构成，第一是Policy function给定状态s后选择的action。第二是State transition function给定状态s和action a后转移到下一个状态s’的概率。 Action-value Function Q(s,a) 给定状态s和action a，这个函数返回的是在这个状态下采取这个action的期望回报。注意这个回报和策略函数π\piπ有关，因为策略函数决定了在这个状态下采取哪个action。 Optimal Action-value Function Q∗(s,a)Q^*(s,a)Q∗(s,a) 选择一个在当前状态和动作下最优的策略函数π\piπ,让期望回报最大。 State-value Function Vπ(s)V_{\pi}(s)Vπ​(s) Vπ(st)V_{\pi}(s_t)Vπ​(st​)是对一个状态的评价，这个评价是基于决策函数π\ ...

网络流的基本概念 网络流问题都是建立在类似上图的有向图之上，有向图的边的权值代表容量。其中A代表源点，C代表汇点，一般考察的问题情景就是从A中流出流量，经过这些有向边，最终汇集到C中。像这样的具有源点和汇点，并且每条边的权值均为正数的有向图就被称作是容量网络，图中的这些边被称作是弧，弧的权值被称作弧的容量，它代表着能够通过这条弧的最大流量。而经过弧上的实际流量被称作弧的流量，所有这些弧的流量所组成的集合就是所谓的网络流。 直观上不难发现符合实际情况的网络流的特点，或者说是限制条件。首先每条弧上的流量不能超过其容量，还有对于除了源点和汇点以外的每个点来说，流入它的流量之和必须与从它流出的流量之和相等，即平衡条件。那么满足这两个条件的网络流就被称作是可行流，可行流的流量定义为从源点所流出的所有流量之和。在所有的可行流中，流量最大的那个被称作是最大流。 对于一串顶点序列(U,U1,U2,U3,…,V)(U,U1,U2,U3,…,V)(U,U1,U2,U3,…,V)，如果满足U是源点，V是汇点，并且序列中每相邻两个顶点之间均存在一条弧，那么就称这个顶点序列为一条链，注意这里并不要求这条弧的方 ...

其实打代码的感觉有点像网络流，重点是推导，剩下就是个板子。 知识点及推导 总结一下算法流程 先推出一般形式 dp[i]=dp[j]+xxxx 展开移项 定义只有i的为b（这样求出b就相当于求dp[i]） 定义只有j的为y（是定点） 对于有i,j的为j项为x，i项为a 现在（x,y）(i之前的)就定下来了 现在维护一个凸包 若q[h]和q[h+1]的斜率比当前a小了，那q[h]就没用了 还有对于队尾的判断，如果q[i]和q[tail]的斜率比q[tail]和q[tail-1]小，那么对于tail也没用武之地了 最后对于状态i的最优策略点j就是q[h]了，O1跟新即可 Updated 2020/09/13 感觉之前写的太片面和肤浅了，这里补一发关于依据单调性的不同做法。 - x,kx,kx,k都是单调的，那么可以方便的直接维护凸包，同时因为凸包斜率单#调，所以决策也有单调性。可以在总复杂度O(n)O(n)O(n)下解决问题 - 只有xxx单调，依然可以建出凸包，但是决策不满足单调性，可以在凸包上二分最佳位置。时间复杂度：O(nlogn)O(nlogn)O(nlogn) ...