This work proposes an approach to evaluating policies that provides tighter performance guarantees if the decision maker's belief happens to be correct, and shows that if computing a policy's worst-case performance is a convex program, then the value of human expertise is equal to the minimax gap of a max-min problem.
Abstract
We consider optimization applications with unknown parameters where the decision maker believes that the optimal value of the nominal problem-the optimization problem they would have solved if the true parameters were known-is unlikely to be large. This belief derives from information that humans have that is not captured in datasets, obtained from domain knowledge and interacting with the physical world. We propose an approach to evaluating policies that provides tighter performance guarantees if the decision maker's belief happens to be correct. Our main result shows that if computing a policy's worst-case performance is a convex program, then the value of human expertise-the maximum improvement in performance guarantees that can be obtained from the belief about the nominal problem-is equal to the minimax gap of a max-min problem. We illustrate our developments in assortment optimization and shortest path problems.
This lecture note develops, from first principles and within a single decision-theoretic setting, the link between the decision objective and the knowledge of an agent and the form of uncertainty representation that is sufficient to act optimally.
This work develops an inverse optimization approach to jointly learn the decision-maker's preferences and the decision rules governing their choices, which leads to better predictions and greater flexibility in capturing and replicating expert decision making.
Anurag Holani, Rishabh Gupta, J. Wassick et al.· 1 citation
Sequential decision-making in real-world applications often involves uncertainty about the environment's model. Uncertain Markov decision processes (UMDPs) represent the possible environments as a set of MDPs with shared states and actions but potentially different transition probabilities and rewards. Optimizing a single policy across all possible MDPs may sacrifice performance, while preparing an individually optimized policy for every MDP may violate operational, regulatory, or interpretability constraints on the number of policies that can be prepared and deployed. We consider settings in which model uncertainty is resolved shortly before execution, allowing the most suitable policy to be selected from a limited set prepared in advance. We introduce $k$-adaptable policy synthesis, which optimizes such a set of $k$ policies under a minimax-regret objective. We prove that the problem is NP-hard and develop KAPS, an exact nested branch-and-bound algorithm with problem-specific bounds and heuristics. KAPS jointly optimizes which MDPs share a policy and the policies themselves. Experiments across various UMDP benchmarks show that the largest reduction in regret consistently occurs when increasing from one to two policies. In the single-policy setting, KAPS is competitive with existing methods in solution quality and proves optimality substantially more often.
Reducing the number of focal elements of a mass function is classically driven by an intrinsic distance, such as Jaccard or Jousselme, that keeps the approximation close to the original as a body of evidence. We consider instead the case where the mass function feeds a linear combinatorial optimisation problem with evidential costs. What should then be preserved is not the closeness of the two mass functions, but the quality of the decision they induce. We introduce a decision-aware approximation that targets the regret of the decision: one decides with the cheaper approximation and is evaluated under the true mass function. On a minimal shortest path, the distance-optimal approximation flips the decision while a decision-aware merge preserves it, and this occurs on a non-negligible fraction of random instances. We prove a one-point bound that localises the regret at the true optimum, turn it into an exact dynamic program for the scalar case, and extend it to an online version that prunes focal elements before the final cost is known. In experiments the decision-aware compressor flips the decision less often than representation-aware compression, for both the linear criterion and a non-linear proxy read-out.
Many design tasks can be cast as black-box function optimization, enabling use of Bayesian optimization to find an ideal design with minimal number of trials. However, often we do not actually need the optimum but instead a sufficiently good solution is enough, for instance a material that is durable enough for its intended use. In most cases there are multiple satisfactory solutions, forming a superlevel set of the function, raising a key question of which one to prefer. We answer this by explaining why robustness to input perturbations that may occur when the solution is deployed is a good criterion and by introduce a Bayesian optimization method that efficiently finds satisficing solutions that are robust to maximally large perturbations. In contrast to previous works, we assume the inputs can be accurately controlled during optimization, but will be perturbed after the deployment.
Samuli Kinnunen, P. Mikkola, Antti Niskanen et al.· arXiv.org· 0 citations
In real-world decision-making problems, one needs to pick among multiple policies the one that performs best while respecting economic constraints. This motivates the problem of constrained best-arm identification for bandit problems where every arm is a joint distribution of reward and cost. We investigate the general case where reward and cost are dependent. The goal is to accurately identify the arm with the highest mean reward among all arms whose mean cost is below a given threshold. We prove information-theoretic lower bounds on the sample complexity for three models: Gaussian with fixed covariance, Gaussian with unknown covariance, and non-parametric distributions of rectangular support. We propose a combination of a sampling and a stopping rule that correctly identifies the constrained best arm and matches the optimal sample complexities for each of the three models. Simulations demonstrate the performance of our algorithms.
Tyron Lardy, Christina Katsimerou, Wouter M. Koolen· Neural Information Processin...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
