Policy invariance under reward transformation

논문 정보

Ng, Andrew Y., Daishi Harada, and Stuart Russell. "Policy invariance under reward transformations: Theory and application to reward shaping." Icml. Vol. 99. 1999.

링크: http://luthuli.cs.uiuc.edu/~daf/courses/games/AIpapers/ml99-shaping.pdf

도입

이번에 공부하게 된 논문은 reward shaping에 관한 논문이다.

reward shaping이란 환경에서 얻을 수 있는 실제 reward를 사용하는 것이 아닌 다른 형태의 reward를 주어 agent 학습을 향상시키는 목적으로 쓰인다.

실제로 많은 환경들이 sparse reward (step마다 나오는 reward가 대부분 0)의 문제를 겪기 때문에 이러한 shaping은 빠른 학습을 도울 수 있다.

 

얼핏 봐서는 당연한 것 같은데 reward shaping을 하기 위해서는 반드시 생각해 봐야할 것이 있다.

"과연 reward shaping 없이 학습시킨 최적의 policy와 reward shaping을 사용하여 학습시킨 최적의 policy가 일치할 것인가?"

reward shaping이라는 것이 결국 환경에 임의의 조작을 가하여 학습을 향상시키는 것이다.

그런데 이 조작 때문에 우리가 배우고자 하는 최적의 policy가 아닌 다른 policy를 배우게 된다면 reward shaping을 하면 안될 것이다.

 

논문에서 잘못된 reward shaping의 예를 들어주는데 다음과 같다.

우리가 자전거를 타고  시작점에서 도착 지점까지 가면 reward를 얻는다고 하자.

그런데 도착지점 전에는 reward가 나오지 않으므로 우리가 임의로 다음과 같은 reward shaping을 했다고 가정해 보자.

"도착지점과 가까워지는 방향으로 움직이면 추가적인 reward를 얻는다."

그러면 agent가 배우게 되는 잘못된 policy 중 하나는 자전거를 타고 계속 같은 자리를 빙글빙글 도는 것이다.

그러면 한바퀴마다 도착지점에 가까워지는 움직임을 취할것이므로 도착지점에 도착하지 않고도 무한대로 reward를 얻을 수 있다.

 

따라서 이러한 잘못된 policy(논문에서는 bug라고 칭했다.)를 피하기 위해 논문에서는 다음과 같은 질문에 답을 해야 한다.

 

"어떤 reward shaping을 하면 original optimal policy와 같은 policy를 학습되도록 보장할 수 있는가?"

논문에서는 간단하게 말한다.

"Potential-based function을 더해주는 방식의 reward shaping을 하면 optimal policy가 동일하다."

위의 식에서 R'가 새로운 reward이고 R은 original reward이다.

추가적인 reward F를 통해서 학습에 도움을 줄 수 있다.

여기서 phi는 potential function으로 우리가 임의로 정할 수 있는 함수이다.

(단, potential은 state에만 영향을 받는 함수이다.)

 

일단, 이렇게 설정하면 위에서 나온 bug는 피할 수 있다.

왜냐하면 빙글빙글 돌 경우 계속 potential의 차이만큼 reward를 추가적으로 얻게 되는데 제자리에 오게 되면 이러한 추가적인 reward의 합이 0이 될 것이기 때문이다.

논문에서 보여주는 증명을 참고하면 기존의 Bellman Equation에 reward shaping부분을 더한 후,

새롭게 Q-function과 value-function을 정의하면 새로운 Bellman Equation을 만들 수 있다.

 

 

그리고 policy는 새로운 Bellman Equation에서 얻은 최대 Q값을 제공하는 action을 취하게 되는데

이 action이 기존 최대 Q값의 action과 일치하므로 (왜냐하면 Q값이 potential function만큼만 shift 됐기 때문이다.)

기존의 최적의 policy와 같게 된다.

Question: 이렇게 argmax로 action을 고르는 방식은 Q-learning에서 쓰이는 것인데 policy gradient에서도 적용할 수 있을까? (참고로 논문에서는 SARSA 알고리즘을 사용했다.)

 

그렇다면 어떤 potential function을 취하면 좋을까?

논문에서는 domain knowledge가 녹아들어간 임의의 potential function을 이용했다.

논문에서 나온 예제 중 한가지만 설명하자면 다음과 같다.

gridworld에서 시작점에서 도착지점까지 최단 거리로 가야하는 환경이 있다.(매 step마다 -1의 reward를 얻는다.)

이 때, 도착 지점과 가까우면 가까울수록 높은 potential이 있다고 정의했다.

즉, 도착 지점과의 manhattan distance를 이용해 potential을 만들었다.

여기서 추가적으로 매 step마다 20%의 확률로 원하지 않는 방향으로 이동하기 때문에 매 step마다 0.8씩 가게 되는 점까지 고려에 넣었다.

 

논문에서는 이 potential을 scale해서 비교해 보는 실험을 해보았는데 scale을 하더라도 reward shaping을 안한 경우보다 굉장히 좋은 성능을 보여주었다.

10x10 gridworld에서 몇번만에 goal에 도착하는지를 나타냈다. 점선은 origianl reward이고, 점+실선은 0.5 potential function을 이용했을 때, 실선은 potential function을 그대로 이용했을 때이다. 보시다시피 potential function을 이용하면 빠르게 최단거리를 학습하는 것을 볼 수 있다.

 

결론 및 느낀점

이 논문에서는 어떤 식으로 reward shaping을 해야 optimal policy를 바꾸지 않으면서도 학습을 향상시킬 수 있을지 보여주었다. reward shaping의 시초격인 논문(무려 1999년 논문이다.)이라 SARSA에 대해서 적용을 했고, 단순한 예제에서만 보여주었기 때문에 후속으로 나오는 reward shaping 논문들이 어떤 식으로 발전했을지 궁금하다. 특히 좀더 학습이 어려운 환경에서 보여주면 좋을 것 같다.