Techniques are described for managing program execution capacity used to execute software programs, such as for a group of computing nodes in use executing one or more programs for a user. Dynamic modifications to the program execution capacity of the group may include adding or removing computing nodes, such as based on automated determinations that previously specified criteria are currently satisfied. The described techniques further include tracking information about changes that occur in one or more capacity utilization metrics of interest in response to dynamic modifications to the program execution capacity of the group, and then using such learned responses to determine a customized capacity modification policy that is configured for the actual operation of the software program(s) for the user. In some situations, the techniques are used in conjunction with a fee-based program execution service that executes multiple programs on behalf of multiple users of the service.