This work contributes an optimization framework in the context of structured interactions between an agent playing the role of a ‘provider’ and a human ‘receiver’. Examples of provider/receiver interactions of interest include ones between occupational therapist and patient, or teacher and student. We specifically consider tasks where the provider agent needs to plan a sequence of actions with a fixed horizon, where actions are organized along a hierarchy with increasing probabilities of success and associated costs. The goal of the provider is to achieve a success with the lowest expected cost possible. In our application domains, a success may be for instance eliciting a desired behavior or a correct response from the receiver. We present a linear-time optimal planning algorithm that generates cost-optimal sequences for given action parameters. We also provide proofs for a number of properties of optimal solutions that align with typical human provider strategies. Finally, we instantiate our general formulation in the context of robot-assisted therapy tasks for children with Autism Spectrum Disorders (ASD). In this context, we present methods for determining action parameters, namely (1) an online survey with experts for determining action costs, and (2) a probabilistic model of child response based on data collected in a real child-robot interaction scenario. Our contributions may unlock increased levels of adaptivity for agents introduced in a variety of assistive contexts.