Introduction
Sequential decision-making under uncertainty is often modeled using Markov Decision Processes (MDPs). However, standard MDPs assume perfect knowledge of transition probabilities and costs. In practice, these parameters are estimated from finite data, leading to epistemic uncertainty. While Nominal (Maximum Likelihood Estimation) approaches perform well with abundant data, they often fail when data is scarce. Conversely, Distributionally Robust MDPs (DR-MDPs) can be overly conservative, optimizing for worst-case scenarios that may be highly improbable.
This paper explores Bayesian Risk MDPs (BR-MDPs), which incorporate a prior belief over model parameters and update this belief as data is observed. Solving infinite-horizon BR-MDPs is traditionally intractable due to the uncountably infinite belief space. We introduce Approximate Bilevel Difference Convex Programming (ABDCP), a novel algorithm that efficiently solves these problems by leveraging difference convex programming and point-based approximations.
Methodology
The ABDCP algorithm addresses the intractability of BR-MDPs through several key technical innovations:
- Bilevel Reformulation: The BR-MDP objective is reformulated as a Difference Convex Program (DCP). This allows the problem to be solved using iterative optimization techniques designed for the difference of two convex functions.
- Point-Based Approximation: Instead of considering the entire belief space, the algorithm maintains a finite set of representative belief states (posterior distributions).
- Iterative Refinement: The set of representative beliefs is dynamically expanded. The algorithm identifies and adds new belief states likely to be encountered by the agent, narrowing the gap between the lower-bound approximation and the upper-bound performance of the resulting policy.
- Finite State Controller: The final policy is implemented as a finite state controller, ensuring computational efficiency during execution.
Experimental Evaluation
The proposed method was evaluated on a Path Planning Problem where an agent navigates a grid to reach a goal while minimizing costs associated with certain cells. The transition dynamics and costs were unknown and estimated from datasets of varying sizes ($N=10$ for high uncertainty and $N=1000$ for low uncertainty).
Results and Key Insights
The experiments demonstrate that ABDCP provides a "sandwich" guarantee, offering both a mathematical lower bound on the optimal value and an upper bound via the generated policy. Unlike static robust methods, BR-MDPs are time-consistent; the agent adapts its risk assessment as it gathers more information.
As shown in the figure above, when data is scarce ($N=10$), the ABDCP-CVaR approach significantly outperforms the Nominal approach. For instance, ABDCP-CVaR ($\alpha=0.8$) achieved an average cost of approximately 75.67, whereas the Nominal approach resulted in a much higher cost of 94.10. The histograms illustrate that the risk-aware policies (a, b, c) successfully shift the cost distribution toward lower values compared to the Nominal baseline (d). Furthermore, as the dataset size increases to $N=1000$, the performance of all methods converges toward the true optimal policy, indicating that the algorithm is consistent.
Conclusion
ABDCP offers a robust framework for Bayesian risk management in infinite-horizon MDPs, filling the gap between overly optimistic nominal models and overly pessimistic robust models. While the current point-based approach is effective for discrete domains like grid worlds, future work will explore function approximation techniques, such as neural networks, to scale the method to high-dimensional continuous state spaces. Additionally, formal analysis of the algorithm's iteration complexity remains an area for further investigation.
Summary updated