[논문 읽기] Effectivs Reinforcement Learning through Evolutionary Surrogate-Assisted Prescription

https://arxiv.org/abs/2002.05368

Effective Reinforcement Learning through Evolutionary Surrogate-Assisted Prescription

Before

RL(Reinforcement Learning) : 강화학습은 에이전트가 환경과 상호작용하면서 보상을 받으면서 자신의 행동을 개선해 나가는 방법.

• 에이전트(Agent): 강화학습에서 환경과 상호작용하며 학습하는 주체.
• 환경(Environment): 에이전트가 상호작용하는 대상이며 에이전트의 행동에 따라 보상을 제공함.
• 상태(State): 환경의 상태. 상태는 에이전트의 행동에 영향을 미치는 정보 포함.
• 행동(Action): 에이전트가 환경에서 수행하는 행동이며, 환경의 상태를 변화시키거나 보상을 얻을 수 있음.
• 보상(Reward): 환경이 에이전트에게 제공하는 보상이며 보상을 최대화 하는것이 목적.
• 정책(Policy): 에이전트가 상태에서 행동을 선택하는 규칙.
• 가치 함수(Value Function): 상태의 가치를 나타내는 함수이며, 에이전트의 행동을 개선하는 데 사용됨.

Abstract

• 조직에서 과거 데이터들을 사용하여 surrogate model을 진화하여 의사결정을 돕고 최적의 결과를 얻을 수 있음.
• 이러한 접근 방식을 ESP라고 함.
• surrogate란 경사하강으로 훈련된 신경망 모델이나 랜덤포레스트와 같은 모델이며, strategy는 surrogate 모델의 예측 성능을 최대화 하기 위해 만들어진 신경망.
  • surrogate 모델은 원본 모델을 대신하여 사용하는 모델로 원본 모델이 복잡하거나, 사용하기 어렵거나, 이해하기 힘들 때 등 이를 사용.(ex : LIME)
• 본 논문에서는 강화 학습(RL)에서의 벤치마크에서 벤치마크 평가를 위해 사용 할 수 있으며, 대부분에 평가는 surrogate에서 이루어지기 때문에 표준 RL 접근법에 비해 높은 샘플 효율과 낮은 분산, 낮은 손해(regret)의 장점을 가짐.
  • regret : 후회라는 뜻인데 강화학습에선 주로 손해 개념으로 많이 쓰임.
• surrogate와 strategy-network가 의사 결정을 정규화 하므로 보다 더 나은 성능을 보이며, 그와 동시에 실생활에 문제에서 유망한 기반을 형성.

Introduction

• 정부, 교육, 의료등 다양한 분야에서 많은 조직들이 데이터를 수집하고 있으며 이를 통해 고객, 소비자, 학생의 행동을 예측하는 모델을 구축할 수 있게 되었음.
• 그러나 예측은 프로세스의 일부일 뿐, 예측 모델은 실제로 최적의 의사 결정이 무엇인지 명시하지 않기에 다양한 접근 방식이 필요함.
• 가장 큰 문제는 최적의 전략을 알 수 없어 gradient-based machine learning 사용이 불가.
  • 변수와 결과는 종종 비선형적으로 상호 작용함.
  • 예를 들어 운동과 영양 섭취와 같은 행동이 병을 치료하는 약에 있어 효과를 더 증진 시킬 수도 있지만 악화 시킬 수도 있음.
• 그래서 더 좋은 의사 결정 전략을 찾아야 하는데 즉, 전략을 생성하고, 평가하고, 그 결과를 바탕으로 더 나은 전략을 생성해야함.
  • 그러나 도메인에 따라 힘들 수도 있음 예를 들면 효과적이지 않는 마케팅을 이용한 홍보, 약물의 치료법을 테스트 하는 데에는 엄청난 비용이 발생.
  • 시물레이션을 통한 방법 또한 많은 양과 계산 시간이 필요할 수 있음.
• 과거의 데이터가 존재하기 때문에 이를 예측 모델을 surrogate로 사용하여 검색이 가능함.
  • 이를 SAO(surrogate-assisted optimization)라고 함.
• Surrogate로도 효율적인 결정 전략은 찾기 어려움.
  • 비선형적인 작용 요소 존재 → 대규모의 변수 동 변경.
  • 최적화하는 변수가 여러개 → 강화학습이 적합하지 않음.
  • 솔루션은 단일 지점이 아니라 전략, 즉 최적의 결정을 매핑하는 함수가 될 수도 있음.
• 위와같은 문제를 해결 하기 위해 evolutionary optimization(진화적 최적화)를 도입한 ESP를 통해 효과적인 솔루션 전략을 발견하기 위한 접근법 개발.
• 이러한 방식은 여러가지 면에서 기존 RL을 개선함. 동일한 수의 에피소드가 주어졌을 때 더 바르게 수렴하여 나은 샘플 효율성, 최적의 성능, 신뢰성이 우수, 비용절감과 같은 효과를 가짐.
• 이 논문에선 다양한 RL 벤치마크에서 ESP 접근 방식을 평가함. ESP의 behavior(행동)은 시각화하여 Predictor(예측자) 와 Prescriptor(처방자)를 같이 학습하고 보여줌.
• ESP는 surrogate의 regularization(정규화, w 가중치 규제 기법)과 함께 다른 predictor모델(ex. random forest)를 데이터에 잘 맞게 함.

Related work

• 전통적인 model-based RL은 시스템의 역학을 구현하고, 현재 상태와 작업을 고려하여 시스템의 다음 상태를 적시에 추정하는 전환 모델을 구축하는 것을 목표로 함..
  1. Agent는 환경에서 데이터를 수집.
  2. Agent는 수집한 데이터를 사용하여 시스템의 역학을 구현하는 전환 모델을 학습.
  3. Agent는 전환 모델을 사용하여 미래의 상태를 예측.
  4. Agent는 예측된 상태를 기반으로 최적 행동을 결정.
  • 전환모델 : 시스템의 현재 상태와 작업을 입력으로 받아 시스템의 다음 상태를 출력하는 모델
• 그러나 model-based RL은 단순한 시스템이라도 수만 ~ 수십만 개의 샘플이 필요함. 이를 해결 하기 위해 PILCO((PRobabilistic Inference for Learning COntrol)와 같은 기술이 개발되었지만 가장 낮은 차원 도메인을 제외한 모든 영역에 대해 계산이 어려움.
  • 어려운 이유 : 높은 차원의 도메인 일수록 전환모델의 모델링해야 할 변수가 많아지기 때문.
  • 사용 알고리즘 : 벨만 최적 알고리즘
• 그렇기에 효율적인 model-free RL이 중요한 대안으로 부상하였으며 성능 및 효율은 보상 추정 방법에 따라 달라짐
• 본 논문에서는 ESP를 DQN과 PPO와 비교할 예정 

  	DQN	PPO
  학습 방식	off-policy	on-policy
  네트워크	Q-Network	Policy Network
  데이터	Q-value	정책
  안정성	불안정	안정적
  적용 환경	복잡한 환경	다양한 환경

• 기존 RL 방법은 심층 신경망에 크게 의존하지만 대조적으로 ESP는 예측자를 블랙박스로 취급하여 많은 경우에 충분한 Random Forest와 같은 모델을 포함하여 모델 선택에 높은 유연성을 허용함.

The ESP Approach

• ESP 접근법의 목표는 일련의 결과를 최적화하는 의사결정 정책을 찾는 것.

$$D(C) = A$$

$$O(C, A)$$

• D = Decision policy
• C = Context
• A = Actions
• O = Outcomes

• C는 환자 A는 약 O는 건강, 비용등이 될 수 있음.
• ESP에서는 Predictor $P_d$ 와 Prescriptor $P_s$ 라는 두 가지 모델이 사용됨.

$$ P_d(C,A)=O' $$

 

$$ \sum_j L(O_j, O_j’) $$

• 이 때 L=Loss function(MSE, Cross_entropy등)이 적용 되었을 때 최소화 하도록 학습이 진행됨

$$ P_s(C) = A $$

 

$$ \sum_{i,j}O'_j(C_i, A_i) $$

 

• 가능한 모든 i에 대하여 최대화가 되도록 함.

• 그리하여 ESP 알고리즘은 Predictor과 Prescriptor를 사용하여 점차적으로 Prescriptor가 진화하는 동시에 Prescriptor를 사용하여 탐색을 유도하여, 사용자는 Prescriptor의 결과를 실제 환경에서 적용하여 데이터를 다시 훈련 데이터로 사용함(out loop).
• Predictor모델은 데이터가 연속형인지 이산형인지, 정형 비정형에 따라 달라지고 해당 논문에선 Randomforest와 Neural networks 사용.
• 반대로 Prescriptor은 복잡한 비선형 매핑을 자연스럽게 표현할 수 있기 때문에 ‘neuro evolution’을 사용함. Prescriptor은 훈련 데이터수와 실제 환경에서 평가할 수 있는 기회의 제약이 없다..
• ESP 프레임워크를 RL 문제에 적용하려면 Context(문맥?) Actions(행동?)을 Suquences로 확장해야함. Prescriptor는 현재 Context를 입력으로 사용하고 각 time step에서 수행할 작업을 결정하는 RL Agent로 볼 수 있음. 즉 Prescriptor의 Output인 $O$’ 는 step에 대한 보상 백터.
• Evolution은 결국 예측된 보상을 최대화 하거나 손해를 최소화 하는것을 목표로함.
• Esp의 out loop는 천천히 변화함 왜냐하면 RL에서 Predictor를 훈련할 데이터 셋이 없기 때문에 현재 Prescriptor에 도메인을 맞춰 데이터를 생성해야함. 그리하여 보다 다양한 훈련 셋을 생성하기 위에 몇몇 우수한 Prescriptor의 elite set이 사용됨.
  1. elite Prescriptor를 실제 도메인에 적용함.
  2. 각 time step에 대한 Q-value 수집.
  3. 2에서 수집한 데이터로 Predictor 학습.
  4. Predictor를 surrogate로 사용하여 Prescriptors를 evolve(진화)시킴.
  5. 수렴할 때 까지 반복.

Experiments

https://gymnasium.farama.org/environments/classic_control/

• Cartpole은 막대기가 쓰러지지 않게 카트를 움직여 균형을 잡는 게임이며 OpenAI가 제작.
  • 막대기가 수직에 가깝게 유지되고 카트가 트랙 중앙에 가까워 질 때 마다 보상이 주어짐.
• 이 논문에서는 Cartpole을 통해 ESP와 다른 RL들과의 비교하여 성능을 입증함.
  • ESP는 2개의 Hidden layer로 64개의 unit, activation funcion은 tanh, output인 하나이며, adam optimizer를 사용하여1000번의 epoch, MSE loss function을 사용하였음.
  • 비교에 쓰이는 DQN과 PPO의 파라미터는 OpenAI의 베이스라인 참조.

• ESP는 다른 RL에 비해 분산이 낮고 더 빨리 수렴 하므로 효율성과 신뢰성이 좋음.
• Regret도 다른알고리즘에 비해 훨씬 낮기 때문에 계산 비용이 줄어들고 안전성 또한 좋음.

 Conclusion

• ESP는 실생활에서 의사결정전략을 발견하기 위해 설계된 방법
• 과거 데이터를 기반으로 surrogate를 학습하고 최소한의 탐색 비용으로 candidate policies(후보 정책)을 평가하는데 사용됨.
• 순차적으로 확장된 ESP는 표본 효율성이 높고 분산이 적으며 Reget도 적으며 신뢰와 안전성을 만들 수 있음.