A Black-Box Multiobjective Optimization Method for Discrete Markov Chains

In this paper, we propose a Newton-inspired black-box optimization algorithm for multiobjective optimization in constrained ergodic Markov chain environments. The method is motivated by challenges in application areas, where decision-making under uncertainty and limited access to structural information is pervasive. A central contribution of the proposed algorithm is the complexity analysis, which yields substantial computational advantages over conventional optimization approaches. Operating in a purely black-box setting, the algorithm relies exclusively on function evaluations and derivative approximations, without requiring explicit knowledge of the objective function’s internal structure. To approximate system dynamics, we employ an Euler-based scheme that enhances the scalability and adaptability of convex optimization problems. While Markov chains are seldom leveraged in black-box optimization, we demonstrate that constrained ergodic Markov chains constitute a powerful and underexplored modeling framework for learning and decision-making under structural constraints. We provide a complexity analysis and illustrate the effectiveness of the proposed method through a numerical example, highlighting its potential to advance applications in multiobjective optimization and decision-making.