Example

이번 chapter에서는 Dynamic programming에 대해서 살펴보았습니다. 앞으로 강화학습을 이해하는데 DP가 상당히 중요하고 실재로 코드를 한 번 봐보고 싶은 분들이 계실 것 같아서 예제를 보여드리려고 합니다.

UC Berkely AI lecture : CS188

http://ai.berkeley.edu/home.html UC Berkely에서도 강화학습 관련하여 좋은 강의가 있다고 Introduction에서 말했었는데 위 사이트가 강의 사이트입니다. 여기서 저희는 Pacman Project 메뉴에서 P3 : Reinforcement Learning을 보도록 하겠습니다.

그 중에서도 저희가 볼 부분은 Question 1 (6 points): Value Iteration 입니다. 이 프로젝트의 코드는 사이트에서 zip으로 다운받으실 수 있습니다. 실재 수업에서 프로젝트로 하는 것인데 다운받은 코드 중에서 학생들이 agent들의 코드를 짜는 프로젝트입니다. 저희는 value Iteration을 하는 agent를 만들면 되는데

valueIterationAgents.py : A value iteration agent for solving known MDPs.

이라는 파일의 내부를 코딩하면 됩니다. 물론 다른 파일들과 연결되어 있으므로 코드를 짜려면 다른 zip안에 있는 파일들도 봐야합니다. 코드는 파이썬으로 되어 있습니다.

풀고 싶은 MDP는 아래 그림과 같습니다. (내용은 agent를 test하는 방법입니다) terminal state가 두 개가 있는데 오른쪽 맨 위의 칸은 1점으로 끝나는 state이고 아래는 -1점으로 끝나는 state입니다. 나머지 state에서 reward는 0입니다. 또한 stochastic하게 앞으로 가려할 때 좌, 우로 각각 10%의 확률로 가게됩니다. discount factor는 0.9입니다.

valueIterationAgents.py라는 파일 내부를 보면 아래와 같이 Your Code Here라고 되어있는 부분들이 있는데 이러한 부분들을 채우는 것이 숙제입니다.

이 사이트에서는 답이 나와있지 않으나 opensource인 만큼 이 문제를 풀어놓은 분들도 계십니다. 처음부터 어떻게 코딩을 해야할 지 모르겠다는 분들은 참고하시면 좋을 것 같습니다. 함께 공부하는 분들이 계시다면 함께 풀어봐도 재밌을 것 같습니다.https://github.com/mkapnick/pacman/blob/master/valueIterationAgents.py

REINFORCEjs : Gridworld DP (Karpathy)

CS231n Convolutional Neural Network 강의로 유명한 Karpathy가 만든 사이트로서 자바스크립트로 위 예제보다는 더 큰 gridworld에서 dynamic programming의 과정을 볼 수 있도록 해놓았습니다. http://cs.stanford.edu/people/karpathy/reinforcejs/gridworld_dp.html

Setting of Example

This is a toy environment called Gridworld that is often used as a toy model in the Reinforcement Learning literature. In this particular case:

State space: GridWorld has 10x10 = 100 distinct states. The start state is the top left cell. The gray cells are walls and cannot be moved to. Actions: The agent can choose from up to 4 actions to move around. In this example

Environment Dynamics: GridWorld is deterministic, leading to the same new state given each state and action

Rewards: The agent receives +1 reward when it is in the center square (the one that shows R 1.0), and -1 reward in a few states (R -1.0 is shown for these). The state with +1.0 reward is the goal state and resets the agent back to start.

In other words, this is a deterministic, finite Markov Decision Process (MDP) and as always the goal is to find an agent policy (shown here by arrows) that maximizes the future discounted reward. My favorite part is letting Value iteration converge, then change the cell rewards and watch the policy adjust.

Interface. The color of the cells (initially all white) shows the current estimate of the Value (discounted reward) of that state, with the current policy. Note that you can select any cell and change its reward with the Cell reward slider.

여기에서 살펴볼 것은 Policy Evaluation 코드와 Policy Update 코드입니다.

• Policy Evaluation

  evaluatePolicy: function() {
  // perform a synchronous update of the value function
  var Vnew = zeros(this.ns); // initialize new value function array for each state
  for(var s=0;s < this.ns;s++) {
    var v = 0.0;
    var poss = this.env.allowedActions(s); // fetch all possible actions
    for(var i=0,n=poss.length;i < n;i++) {
      var a = poss[i];
      var prob = this.P[a*this.ns+s]; // probability of taking action under current policy
      var ns = this.env.nextStateDistribution(s,a); // look up the next state
      var rs = this.env.reward(s,a,ns); // get reward for s->a->ns transition
      v += prob * (rs + this.gamma * this.V[ns]);
    }
    Vnew[s] = v;
  }
  this.V = Vnew; // swap
  },

  각 state마다 가능한 action에 대해서 policy evaluation를 진행합니다. 각 state의 update될 값들을 행렬로 저장해놓고 있다가 모든 state에 대한 update값이 다 계산이 되면 한 번에 swap하는 형태입니다.

• Policy Update

  updatePolicy: function() {
  // update policy to be greedy w.r.t. learned Value function
  // iterate over all states...
  for(var s=0;s < this.ns;s++) {
    var poss = this.env.allowedActions(s);
    // compute value of taking each allowed action
    var vmax, nmax;
    var vs = [];
    for(var i=0,n=poss.length;i < n;i++) {
      var a = poss[i];
      // compute the value of taking action a
      var ns = this.env.nextStateDistribution(s,a);
      var rs = this.env.reward(s,a,ns);
      var v = rs + this.gamma * this.V[ns];
      // bookeeping: store it and maintain max
      vs.push(v);
      if(i === 0 || v > vmax) { vmax = v; nmax = 1; }
      else if(v === vmax) { nmax += 1; }
    }
    // update policy smoothly across all argmaxy actions
    for(var i=0,n=poss.length;i < n;i++) {
      var a = poss[i];
      this.P[a*this.ns+s] = (vs[i] === vmax) ? 1.0/nmax : 0.0;
    }
  }
  },

Greedy action improvement로서 각 state에서 value function이 가장 큰 다음 state(value function더하기 reward)를 선택하는 policy를 생성합니다.

이 두가지를 반복함으로서 Policy Iteration 알고리즘이 되는 것입니다.