  With the goal to provide absolute lower bounds for the best possible running
times that can be achieved by $(1+\lambda)$-type search heuristics on common
benchmark problems, we recently suggested a dynamic programming approach that
computes optimal expected running times and the regret values inferred when
deviating from the optimal parameter choice.
  Our previous work is restricted to problems for which transition
probabilities between different states can be expressed by relatively simple
mathematical expressions. With the goal to cover broader sets of problems, we
suggest in this work an extension of the dynamic programming approach to
settings in which the transition probabilities cannot necessarily be computed
exactly, but in which they can be approximated numerically, up to arbitrary
precision, by Monte Carlo sampling.
  We apply our hybrid Monte Carlo dynamic programming approach to a
concatenated jump function and demonstrate how the obtained bounds can be used
to gain a deeper understanding into parameter control schemes.
