  We use the technique of information relaxation to develop a duality-driven
iterative approach to obtaining and improving confidence interval estimates for
the true value of finite-horizon stochastic dynamic programming problems. We
show that the sequence of dual value estimates yielded from the proposed
approach in principle monotonically converges to the true value function in a
finite number of dual iterations. Aiming to overcome the curse of
dimensionality in various applications, we also introduce a regression-based
Monte Carlo algorithm for implementation. The new approach can be used not only
to assess the quality of heuristic policies, but also to improve them if we
find that their duality gap is large. We obtain the convergence rate of our
Monte Carlo method in terms of the amounts of both basis functions and the
sampled states. Finally, we demonstrate the effectiveness of our method in an
optimal order execution problem with market friction and in an inventory
management problem in the presence of lost sale and lead time. Both examples
are well known in the literature to be difficult to solve for optimality. The
experiments show that our method can significantly improve the heuristics
suggested in the literature and obtain new policies with a satisfactory
performance guarantee.
