Dynamic Release Management of Product Features

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 improving rival. 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 current quality of the rival product. Computing such a policy amounts to solving a related deterministic release-sequencing problem, and we apply an exchange argument to obtain an index condition necessary for optimality. In the simplest case we consider, a heuristic based on this condition reduces to an optimal ordering of Gittins indices and is equivalent to the weighted discounted shortest processing time first stochastic scheduling rule. 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 value function approximation motivated by the case without fixed costs. We show that the resulting policy can provably outperform an intuitive certainty-equivalent heuristic by an arbitrarily large margin. Our policy also performs within 3% of optimality across a range of numerical trials.