Approximation is a fundamental property of applications that need to be productive in uncertain and resource-constrained environments. Applications are configured to maximize outcome quality while respecting a budget. Current approaches rely on extensive off-line training to determine trade-off spaces. We introduce a graph representation, the RSDG, that exposes the approximation levels and dependencies. RSDG enables an efficient training phase, and formulates the problem as a constrained optimization problem. We have implemented RAPID, a programming framework that defines and executes RSDGs. RAPID dynamically adjusts the application behavior, updates the cost model, and optimizes groups of applications in multi-application environments.