[MDP] Linear Programming

recoder·2022년 4월 21일
0
  • 아래는 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
profile
기억은 나 대신 컴퓨터가

0개의 댓글