2018년 10월 10일 수요일

강화학습(Reinforcement Learning)으로 접근하는 E-commerce Dynamic Pricing 논문리뷰

요즘 취미생활중인 강화학습!
강화학습의 코딩 Deep Dive 를 하기 위한 Play Ground 를 뒤지던 중, 우리 파트, deep learning specialist 한성국파트너가 좋은 논문을 소개해 주었다.

일단, 나의 기준으로 좋은 논문
(1) Goal 이 Practical 한지,
(2) 구현 가능할 것 같은지,
(3) Goal 뿐 아니라, 구현 난이도 등에서도 현실성을 갖추고 있는지(너무 두리뭉실하게 표현하고, 많이 숨기고 있으면 탈락이다.)...

에 가중치를 높게 두고 있음을 알려둔다. (물론 저 기준은 산업계에 몸담고 있는 나의 지극히 개인적인 기준일 뿐이다. 저런 류의 Practical 한 논문 또한 Ideal 한, Research 논문을 바탕으로 그 위에 등장할 수 있으므로, 모든 Research 논문들이 결국은 뿌리이며, 진화의 시작이라 할 수 있다.)

이 논문은 아직 학술적으로는 검증된 논문이 아니다. ICLR 2019 에 제출되었으나, 아직 Review 중인, 그래서, 저자가 누구인지도 모르는 상태의 논문이기 때문이다.

하지만, 내용을 읽다 보면, 실무에서 바로 적용하기 위한 연구를 진행하였고, 그 과정에서의 시도와 결과 그리고 인사이트 등을 경험을 통해 공유하고 있음을 알수 있다. 더군다나 Tmall.com (By Taobao) 이라고 하는 걸출한 E-commerce 플랫폼 위에서 꽤 많은 양의 데이타와 기간으로 실험한 결과를 보여주고 있어, 검증 자체에도 강한 신뢰가 가는것이 사실이다.

이런류의 논문은 학술적인 가치를 논외로 치더라도, 그 실험 방법, 문제의 정의, 그리고, 그것을 적용한 결과 자체가 매우 Practical 하여, 이런류의 문제를 동일하게 Real World 에서 접근 시 매우 큰 참고가 될 수 있어서 좋다.
(아마도 저자는 Taobao 의 직원일 것이다. 꼭 그렇지 않더라도, 해당 플랫폼 위에서의 실험 자체가 Real World 를 많이 반영하고 있어서 맘에 든다.)

본론으로 들어가서 내가 읽은 부분을 요약해 보겠다.

  1. 논문 제목
    1. DYNAMIC PRICING ON E-COMMERCE PLATFORM WITH DEEP REINFORCEMENT LEARNING
  2. 논문 위치
    1. https://openreview.net/pdf?id=HJMRvsAcK7
  3. 서론부에 등장하는 타사 사례
    1. Uber 사례
      1. Uber 는 'surge' 라고 하는 dynamic pricing 전략을 구현하고 발표한바 있는데, driving time 을 늘리는데 있어 매우 큰 기여(significant impact)를 줬다고 한다.
      2. [사족] @김상우 님. 저희 예전에 쏘카에서 Reinforcement Learning 으로 dynamic Pricing 적용 시의 파급효과및 구현 가능성에 대한 대화를 잠시 나눈적 있었죠? 딱 그 모델이네요. 물론 Uber 는 다른 알고리즘을 사용했을지도 모르지만요...
      3. Chen & Sheldon (2016) 에서 소개되었다.
    2. Zara 사례 
      1. systematic 한 dynamic pricing 모델을  구현 적용하였으며, Markdown pricing strategy 에  적용.
      2. Caro & Gallien (2012) 에서 소개.
      3. [사족] Markdown은 좀 옛 방식이긴 하지만, 여전희 Off-line 등에서 Human 에 의해 직관으로 대부분 수행되고 있으며, 국내 E-commerce 에서는 이 조차도 Model 화 되지 않은 곳이 대부분이다.(2018년 현재 기준). 기술이 어렵다기 보다는 실행력이 어려운 분야가 또 이 분야일 것이다. 가격과 관련된 프로젝트는 장고를 뒤따르게 만들기도 하거니와, 책임, 위험부담 등등, 넘어서야 하는 것들이 많은, 기술 이외의 것들이 더 어려운 분야가 또 이 분야이다. Zara 방식 소개 논문이 2012년 인것으로 보아, 벌써 6년 전 이므로, Zara 는 지금 이 분야가 매우 진화 되어 있을 것으로 추측 된다.
    3. Kroger 사례
      1. Offline 에서 Dynamic Pricing 을 적용하고 개선하기 위해, Electronic price tag 를 스토어에 적용 개선 중.
      2. Nicas (2015)
      3. [사족] 매우 오래전, 벌써 3년전에 Off에서조차 이런시도를 했으니, 그때부터 Kroger 는 매우 발빠른 유통기업이었던거 같다. 현재(2018년)의 Kroger  는 Google에서 무인자동차를 하던 핵심멤버들이 나와서 창업한 실리콘벨리의 무인자동차 관련 Startup 과 제휴하여, 무인배송자동차를 통한 유통 혁명을 실험하고 있고, 아마존 월마트 못지 않게 Data 를 잘 다루는 선진적인 유통기업의 면모를 다양한 곳에서 보여주고 있다. 아니나 다를까... 2015년 부터 이런 시도를 했었넹....  
    4. Amazon.com 상품수
      1. 2017년 기준 562 million = 5억 6천 2백만 상품이 있다고 함.
    5. Wallmart.com 상품수
      1. 4.2 millon = 420만 상품이 있다고 함. ([사족] 뭐 별거 아니네....물론 온라인전용 상품 포함이 아닌 오프라인 상품 수가 저 정도라고 한다면, 말이 다르지만...)
    6. Taobao.com 상품수
      1. 2 billion = 20억 상품.
      2. ([사족] 중국이 대단한건 알고 있었지만, World Top Level 아마존이 5억 6천인데.... 2017년이라고 하더라도, China Top Level 타오바오가 20억 상품 이라뉘.... 물론 Tmall 은 이미 Global 화가 많이 진행되고는 있지만...)
    7. Amazon.com 사례
      1. Automatic Pricing System 을 만들었음.
      2. 매 15분 마다 Price를 갱신. (2016년 기준)
      3. Chen et al. (2016)
    8. 학계의 Approach 
      1. 기존연구들
        1. Statistical Learning. 
        2. price optimization.
        3. stochastic model.
        4. Bayesian dynamic pricing policies.
        5. non-parametric approaches.
      2. 위 연구들은 큰 한계가 있었음.
      3. 그 한계를 뛰어 넘는 최신 연구.
        1. MAB(multi armed bandit) 을 이용. Misra et al. (2018) 
        2. 본 논문은 MAB 를 그래서, base model 비교군으로 삼았음.
  4. 본 논문의 알고리즘 요약
    1. Dynamic Pricing Problem 을 Deep Reinforcement Learning 으로 접근.
    2. E-Commerce 플랫폼에 적용하여 evaluation. (taobao 의 Tmall.com)
    3. 주요접근 방법
      1. Markov Decision Process 를 이용한 D.P. 의 첫 논문이라고 밝힘.
        1. [사족] 이 시점 부터 AlphaGo-Lee(이세돌버전)가 강하게 떠오른다. Alphago-Lee 는 Markov Decision Process 를 활용한, Monte Carlo tree search , 그리고 마찬가지로 Deep Reinforcement Learning 이 주요 알고리즘들 중 하나이다.
      2. discrete and continuous 한 price 액션 스페이스 에서 다양한 보상 functions 을 정의.
        1. discrete pricing action model
          1. deep Q-networks (DQN) 이용.
        2. continuous pricing action model
          1. (DQN) 과 함께 Deep Deterministic Policy Gradient (DDPG) 가 이용.
      3. historical data 로부터 pre-train 모델을 적용.
        1. pre-training 의 중요성이 길게 언급되었었음.
    4. pricing period d 는 하루나 한주가 될 수 있음.
    5. 보상(reward) function 은 revenue 혹은 sales. 수익 혹은 매출로 가능하지만...
      1. 그러나 위 두 값은, 요일, 계절, 행사 및 이벤트 여부 등 다양한 외부 변수에 의하여 매우 가변적인 값이다.
      2. 그러한 값들에 독립적인 measure 가 필요.
      3. 본 논문에서는 이를 revenue conversion rate 로 칭하였고, 다음과 같이 정하였다.
        1.   dividing revenuei by uvi -> 이를 시간에 따른 변화량으로 표현.
    6. 다양한 features
      1. price features
      2. sales features
      3. customer traffic features
      4. competitiveness features
        1. [사족] 경쟁사의 동일 상품의 상태는 중요하고 상관도 높은 feature 일 수 있는데, 유일한 외부 feature 이기도 하다.
        2. [사족] 그래서, 크롤링이 동원되어야 하고, 크롤링 해서 가져올 내용은 경쟁사 가격, 행사 및 이벤트 여부, 그리고 댓글 달리는 속도(이는 조회 수를 유추 할 수 있어서...)
        3. 저자 역시 이런 언급을 했다.  
          1. The comments and the states of the similar products contribute to competitiveness features. 
  5. 실험결과
    1. Offline 결과
      1. 4만개의 서로 다른 fast moving consumer product 를 사용
      2. 60일 판매데이타 사용
        1. 59일을 가지고 pre-training 
        2. 마지막 1일을 가지고 evaluation
      3. 240만 튜플이 이용되었다.
      4. offline policy evaluation 에서 MAB 알고리즘 구현체로 LinUCB 를 사용. 이는 Deep Reinforcement Learning 을 앞도했음.
        1. MAB 는 즉각적인 reward 를 maximize 하는 경향 있음.
        2. DRL 은 long-term reward 를 maximize 하려는 경향 있음.
        3. 이는 offline 의 특성에 기인.
        4. 하지만, E-commerce 플랫폼에서는 이 optimal policy 는 적합하지 않음.이는 뒤이는 online 결과에서 입증 됨.
      5. 서로다른 accuracy 모델(error rate, rate of right estimation, etc)에서는 DRL 이 더 높은 accuracy 를 보임.
    2. Online 결과
      1.  revenue  conversion rate 와  profit conversion rate 모두 DQN 이 사람의 manual 판단을 앞도 했음.
      2. 유사 상품 그룹은 유사 결과를 보여준다는 것(a)과 DQN과 LinUCB 를(b) 그리고 다시 DQN과 DDPG 를(c) 비교하였음.
  6. 결론
    1. DDPG와 DQN 로 구현한 pricing policies는 기존의 다른 pricing policies 를 앞도하였다.
    2. markdown pricing 에 있어서도 deep reinforcement learning approach 가 기존 manual markdown pricing strategy 를 앞도하였다.
    3. 본 연구에서는 각각 개별 상품별로 pre-training 을 수행했다.
    4. 그러므로, 잘 팔리지 않는 상품에 대하여는 별도의 처리를 해주어야 하며, 이 부분은 transfer learning 및 meta learning 기법이 이용될 수 있다.
    5. 향후 promotion pricing feature 와 membership pricing fetures 를 추가할 예정이다.
    6. [사족] 본 논문은 다이나믹 프라이싱을 Markov Decision Process 를 사용하여 가장 최신의 기법인 MAB 기법보다 낳은 결과를 보여주었음을 보여주었다.
    7. [사족] 이 논문이 읽는 독자의 시각에서 크게 기여하고 있는 바는 아래 정도일 듯 한다. 내가 느낀 바 이다.
      1. Pricing 문제를 RL 로 접근함에 있어, 문제정의 그리고 접근 방법에 충실한 가이드라인을 제공하고 있다.
      2. 시간단위별 revenue conversion rate 를 가지고 reward function을 만든 부분은 간단하면서도 꽤 reasonable 한 approach 였다.
      3. 중요 feature 들을 잘 정리해주었고, 유사상품 그룹의 특성까지 실험해 주었다.
      4. 어느정도의 데이타로 어느정도의 결과에 도달하는지 가이드를 제시해 주었다. 향후 이 수치는 우리가 맞게 접근하고 있는지 가늠하는데 큰 도움이 될 수 있다.
      5. 접근한 DQN 과 DDPG 의 hyper parameter 도 제시하고 있다. 유레카~~ ^^
    8. [사족] 내가 이런류의 Practical 한 논문을 좋아하는 이유는 이를 그대로 구현해 보는 것이 최초의 Base line 모델 구축 이후 다음 2번째 혹은 3번째 시도 정도로서 매우 빠르고 유용한 접근 가이드를 제시하기 때문이다.