Abstract: We consider a release manager who sequentially releases new versions of her product by drawing from a fixed and non-replenishable finite set of features while facing an exogenous, stochastically evolving marketplace. In the absence of fixed costs, we provide conditions under which there exists a quasi-open-loop optimal policy, i.e., an optimal policy that depends only on the set of available features and not the state of the external market. This approach applies to a broad set of problems, and allows practitioners to increase the fidelity of a model without sacrificing tractability. In the context of release management, computing such a policy amounts to solving a related deterministic release-sequencing problem. In the simplest case we consider, an index-based policy equivalent to an ordering of Gittins indices is optimal. However, we prove it is suboptimal by an arbitrarily large margin in other settings. We apply approximate dynamic programming
(ADP) to address the case with positive fixed costs by making a novel value function approximation motivated by the case without fixed costs.
The resulting policy can provably outperform an intuitive certainty-equivalent heuristic by an arbitrarily large margin, and performs within 3.5% of optimality across a range of numerical trials.
- Tags
-