[MDP] Linear Programming

• 아래는 linear programming 방식으로 MDP를 푸는 식이다.

  • LP 방식은 이미 개발된 여러 알고리즘을으로 풀 수 있다.

• 이 식의 unique optimal solution은 optimal value function
  

• 풀어서 쓰면 아래와 같다.
  

policy evaluation via LP

Appproximate optimal value function

• large scale problem의 경우 basis function으로 근사한다.
  
• matrix form
  
• basis function은 domain knowledge로 디자인해야한다.
• 요즘은 NN을 많이 활용한다.
• 일부 constraint만 뽑아서 사용한다.
• 장점
  • decision variable 수 n -> k 로 감소
• 단점/한계
  • constrain 수는 그대로
  • loss of optimality
• 참고
  • error bounds
  • constraint sampling