DQN experiment: Pong
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, ...
演化算法HW4 BBO黑箱芯片放置问题
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
《深度强化学习》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
浅析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
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)
...
快速傅立叶变化FFT
FFT是一种可以在O(n∗logn)O(n*log_n)O(n∗logn)的优秀时间复杂度里,求出两个多项式乘积的优秀算法。
首先,我们如何表示一个(n−1)(n-1)(n−1)次多项式?
用每一项的系数来表示
用n个点的坐标来表示
所以算两个多项式乘积时,如果暴力计算系数,是O(n2)O(n^2)O(n2)的。
但是如果我们有这两个已知多项式的点的表达式,那么我们只需要O(n)O(n)O(n)的时间就可以得到带求多项式的点表达式。
不幸的是,为了得到两个多项式的n个点坐标,在横坐标随记下我们仍需要O(n2)O(n^2)O(n2)的时间来完成。
所以有没有什么办法可以优化找点的过程了。
以为名叫傅里叶的牛人发现了复数可以完美解决这个问题。
具体来说,我们再复数坐标戏中引入单位元(类比三角函数),因为复数有个性质,两复数乘积的几何意义是模长相乘,辐角相加。
因为我们取得点在单位圆上,于是同一个复数的nnn次乘积在几何意义上表现为辐角的成倍增长。
前方高能,我们开始搞事情了。
设带求多项式为F(x)
我们按照多项式次数的就分成两节。
即F(x)=FL(x2)+x∗FR(x2) ...
SAM 后缀自动机
(p.s: code是真的短)
从头开始的详细版见WiKi
主要的难点都在后缀边和点的划分上。
重新声明一下定义:
我们按照这个字串在原串中每一个出现的最后一位的位置集合为一个点,即一个点里可以包含多个字串,我们钦定每个点中最长的字串长度为lenilen_ileni。
后缀边 按照点的集合定义,后缀边其实是把这些点按照集合包含关系连了起来(只会连所有包含关系中len最小的那个点),即成一棵树。
然后就好办了啊
建立SAM算法流程简析
首先建立前缀的节点,集合只有前缀本身
从上一个前缀节点开始向上搜索看有没有点有新加入字符的正向连边。(注意正向连边图是一个DAG)
分三种情况:
若全没有,则该字符没出现过,fa->root即可
找到存在p,设q为p的该字符的对应点,
若 len[p]+1==len[q]len[p]+1==len[q]len[p]+1==len[q] ,因为p是原来串的最长可以跟字符s的点,原串与新串差1,如果len也差1,那么q必定是包含新串最长的点。
现在没发再特判了,需要新建立一个点来解决问题。
这个点继承q点后面 ...
无旋treap(fhq)
之前写过一篇按权值的fhq,可以解决查询前驱后继,第k大等操作。
不过如果我们把fhq的特性转移到数列上,即类比线段树储存sum,标记之内,那么又是一个新毒瘤数据结构了。
补:(一些对FHQ的理解)
一共只有n个节点,不像线段树有2n个左右,因为fhq节点的左右儿子都是直接的节点(而线段树需要辅助节点),同时如果是对序数fhq,中序遍历就是当前数组,而对权值fhq,中序遍历是从小到大的顺序。
split的时候,两个取址的参数是分别两个分裂子树的root,注意,他们是完全分割的两个东西,并没有直接联系,第一层分裂完后,下一个该归到同一个分裂fhq的作为它的左右儿子。
一些注意事项:
FHQ的正确性基于满足中序遍历和堆性质的树的形态是固定的。
pushdown操作如果要改变子树形态或者siz大小,需要小从把标记推完后,再进行操作。
毒瘤板题传送门
我们知道线段树可以实现区间和,区间更改,最大子段和等操作,但此题还要求加入一串数、删除一串数、翻转一串数的操作。
现在思考一下如何用fhq解决以上问题。
fhq本身由插入顺序决定相对位置(因为其本身是一棵二叉搜索树 ...