The specification of a Markov Decision Process(MDP) can be difficult. In many case, a specified MDP problem has uncertainty on reward function or transition function. It is important to know the sensitivity of an optimal policy given a uncertain MDP. I propose how to calculate the range of uncertainty of MDP model parameters such that a current optimal policy is still optimal after the MDP has changed. It is known that the precise specification of reward functions of MDPs is often extremely difficult. Recent works show that minimax regret decision criterion is suitable for computing a robust policy of a reward-uncertain MDP. I propose an novel algorithm to compute a robust policy in reward-uncertain MDPs using nondominated policies over the feasible reward space. My algorithm uses the result of sensitivity analysis of a given rewarduncertain MDP, and finds the nondominated policy set exactly and faster than previous works. I also suggest approximation algorithm to compute the approximated nondominated policy set. My experimental results suggest that by using the result of sensitivity analysis, it is possible to get (near-)optimal minimax regret policy very quickly.
Markov Decision Processes(MDPs)는 확률적인 환경에서 연속적인 의사 결정을 필요로 하는 문제를 다루는 데에 매우 효과적인 모델이다. MDP로 모델링 한 문제는 value iteration, policy iteration과 같은 알고리즘을 통해 최적행동정책을 구함으로써 효과적인 의사 결정을 할 수가 있다. 그러나 해결하고자 하는 문제를 MDP 모델로 구체화 하는 일은 상당히 어려운 일이다. 또한 모델링한 MDP의 매개변수의 값들은 불확실성을 포함하고 있을 수 있으며 그 불확실성에 의해 최적행동정책이 변할 수 있다. MDP의 민감도분석이란 모델링한 MDP의 매개변수들이 불확실성에 의해서 모델링한 값과 실제 값에 차이가 존재할 경우 그 차이가 최적행동정책의 변화에 미치는 영향을 분석하는 것이다. MDP의 민감도분석을 통해 주어진 문제의 구체화에 불확실성이 포함되어 있어서 전이확률함수 혹은 보상함수의 값이 실제 값과 차이가 존재하더라도 현재 구체화한 모델의 최적행동정책이 여전히 최적일 수 있는 차이의 범위를 알 수 있게 된다. 그리고 그 결과를 통해 모델의 불확실성에 대해 안정적인(robust) 행동정책을 구할 수 있다. 본 논문에서는 보상함수에 불확실성이 존재하는 MDP에 대해서 민감도분석을 수행하는 방법을 제안할 것이다. 또한 이를 통해 안정적인 행동정책을 구하는 데에 있어서 기존에 제안된 알고리즘보다 속도가 빠른 새로운 알고리즘을 제안할 것이다.
