Q-learning, a cornerstone of reinforcement learning, is the quest of an agent to master its environment by discerning the quality of its actions. Through iterative experiences, the agent constructs a map of rewards, forging paths to optimal outcomes.

Critic

  • A critic does not directly determine the action.
  • Given an actor π\pi, it evaluates how good π\pi is.
  • There is an actor called state value function Vπ(s)V^{\pi}(s)
    • When using π\pi (to interact with env), the cumulated reward is expected after visiting state ss.

It literally just make a prediction. Having VπV^{\pi} to look into the state ss, then yields a scalar, Vπ(s)V^{\pi}(s).

Output of a critic depends on the evaluated actor.

Another Critic

  • State-action value function Qπ(s,a)Q ^{\pi}(s, a)
    • When using actor π\pi, the cumulated reward is assessed after taking action a at state s

Policy π\pi is a network with parameter θ\theta.

  • Input: the observation of machine represented as a vector or a matrix.
  • Output: each action corresponds to a neuron in output layer.

From the previous article, Trajectory τ={s1,a1,s2,a2,...,sT,aT}\tau = \lbrace s_1, a_1, s_2, a_2, ..., s_T, a_T \rbrace. For every trajectory, its probability can be calculated ( given the parameters θ\theta of the actor ):

pθ(τ)=p(s1)pθ(a1∣s1)p(s2∣s1,a1)pθ(a2∣s2)p(s3∣s2,a2)...p_{\theta}(\tau) = p(s_1)p_{\theta}(a_1|s_1)p(s_2|s_1, a_1)p_{\theta}(a_2|s_2)p(s_3|s_2,a_2)... =p(s1)∏t=1Tpθ(at∣st)p(st+1∣st,at)= p(s_1)\prod_{t=1}^{T}p_{\theta}(a_t|s_t)p(s_{t+1}|s_t, a_t)

p(st)p(s_t) depends on the behavior of the environment, which can NOT be controlled.

Also, there is reward rtr_t, R(τ)=∑t=1TrtR(\tau)=\sum_{t=1}^{T}r_t

The objective is to adjust θ\theta to maximize R(τ)R(\tau). However, reward is a random variable (r.v.), due to the stochasticity of actor and environment (actor at a given state ss gives some random action aa, and so is environment). Expected Reward is calculated.

Rˉθ=∑τR(τ)pθ(τ)=Eτ∼pθ(τ)[R(τ)]\bar{R}_θ = \sum_τ R(\tau)p_θ(\tau) = E _{\tau \sim p _{\theta}(\tau)}[R(\tau)]

Policy Gradient

Rˉθ=∑τR(τ)pθ(τ)\bar{R}_{\theta} = \sum_{\tau} R(\tau)p_{\theta}(\tau), ∇Rˉθ= ?\nabla \bar{R}_{\theta} = \ ?

∇Rˉθ=∑τR(τ)∇pθ(τ)\nabla \bar{R}_θ = \sum_τ R(\tau)\nabla p_θ(\tau)

R(τ)R(\tau) do not have to be differentiable, can even be a blackbox (Similar to GAN 🧐)

∇Rˉθ=∑τR(τ)pθ(τ)∇pθ(τ)pθ(τ)=∑τR(τ)pθ(τ)∇log⁡pθ(τ)=Eτ∼pθ(τ)[R(τ)∇log⁡pθ(τ)]≈1N∑n=1NR(τn)∇log⁡pθ(τn)\begin{aligned} \nabla \bar{R}_{\theta} &= \sum_{\tau} R(\tau) p_{\theta}(\tau) \frac{\nabla p_{\theta}(\tau)}{p_{\theta}(\tau)} \\ &= \sum_{\tau} R(\tau) p_{\theta}(\tau) \nabla \log p_{\theta}(\tau) \\ &= E_{\tau \sim p_{\theta}(\tau)}[R(\tau) \nabla \log p_{\theta}(\tau)] \\ &\approx \frac{1}{N}\sum_{n=1}^{N} R(\tau^n) \nabla \log p_{\theta}(\tau^n) \end{aligned} 1N∑n=1N∑t=1TnR(τn)∇log⁡pθ(atn∣stn)\frac{1}{N}\sum_{n=1}^{N} \sum_{t=1}^{T_n} R(\tau^n) \nabla \log p_{\theta}(a_t^n | s_t^n)

Note: ∇f(x)=f(x)∇log⁡f(x)\nabla f(x) = f(x)\nabla \log f(x) (logarithmic derivative). env component in pθ(τ)p_{\theta}(\tau) is not related to θ\theta, therefore only do gradient ∇\nabla on log⁡pθ(atn∣stn)\log p_{\theta}(a_t^n | s_t^n).

Intuitively, among ALL sampled data, at a certain state sts_t an action ata_t is to be executed ((at∣st)(a_t | s_t) is SOME state and action pair within the trajectory) results in the trajectory τ\tau. if certain (at∣st)(a_t | s_t) pair results in some positive reward in the trajectory, then increase the likelihood of the pair and vice versa.

More Math

θ←θ+η∇Rˉθ\theta \leftarrow \theta + \eta \nabla \bar{R}_{\theta} ∇Rˉθ=1N∑n=1N∑t=1TnR(τn)∇log⁡pθ(atn∣stn)\nabla \bar{R}_{\theta} = \frac{1}{N}\sum_{n=1}^{N} \sum_{t=1}^{T_n} R(\tau^n) \nabla \log p_{\theta}(a_t^n | s_t^n)

Cycles of data collection and model updates --- Policy is noted as πθ\pi_{\theta} (using existing agent θ\theta to interact with the environment)

Using game as an example, in game play one τ1\tau^1, going through (a11∣s11)(a_1^1 | s_1^1), (a12∣s12)(a_1^2 | s_1^2), … results in R(τ1)R(\tau^1), then for game play two τ2\tau^2 (just change the superscript), etc. Using those data collected to calculate ∇Rˉθ\nabla \bar{R}_{\theta}

Essentially, plug in ALL the (s∣a)(s|a) pairs to calculate its log probability, get the gradient, then multiply by a weight, which is the reward that is collected from a game play.

Extra Tips

Add a Baseline

  • θ←θ+η∇Rˉθ\theta \leftarrow \theta + \eta \nabla \bar{R}_{\theta}, its possible that R(τn)R (\tau^n) is always positive.
  • ∇Rˉθ≈1N∑n=1N∑t=1TnR(τn)∇log⁡pθ(atn∣stn)\nabla \bar{R}_{\theta} \approx \frac{1}{N}\sum_{n=1}^{N} \sum_{t=1}^{T_n} R(\tau^n) \nabla \log p_{\theta}(a_t^n | s_t^n), according to the equation (and explanation in the previous section), likelihood of pθ(atn∣stn)p_{\theta}(a_t^n | s_t^n) shall increase if it provides a positive R(τ)R(\tau)

Due to the nature of sampling (ONLY some (atn∣stn)(a_t^n | s_t^n) pair can be sampled, therefore the probability of the un-sampled actions will decrease), a baseline term b≈E[R(τ)]b \approx E[R(\tau)] can be used.

∇Rˉθ≈1N∑n=1N∑t=1Tn[R(τn)−b]∇log⁡pθ(atn∣stn)\nabla \bar{R}_{\theta} \approx \frac{1}{N}\sum_{n=1}^{N} \sum_{t=1}^{T_n} [R(\tau^n) - b]\nabla \log p_{\theta}(a_t^n | s_t^n)

Assign Suitable Credit

Instead of calculate the sum of rewards in the ENTIRE τ\tau, it is BETTER to obtain the sum of rewards after a certain action performed

Use ∑t′=tTnrt′n\sum_{t'=t}^{T_n} r^n_{t^{\prime}} represent the sum of rewards from time tt (where the action was performed) till the end of the game.

We can even take one step further by adding a discount factor for rewards on more future rewards on the current action γ<1\gamma \lt 1, yields ∑t′=tTnγt′−trt′n\sum_{t'=t}^{T_n} \gamma^{t'-t}r^n_{t^{\prime}}. It is reasonable because rewards collected not too long after an action should be weight MORE than later rewards.

Advantage Function

Eventually, R(τn)−bR(\tau^n)-b becomes Aθ(st,at)A^{\theta}(s_t, a_t).

It measures how good it is if we take ata_t other than other actions at sts_t. θ\theta indicates the nature that it goes through a network.