A hosted service may include multiple applications and have a large number of active features, each in varying stages of deployment, that are gradually rolled out in one or more deployment environments. The hosted service may include a flight state machine, which may provide policy based flight management for feature rollout. For example, in response to receipt of a flight request associated with a feature of the hosted service, the flight state machine may be configured to retrieve a policy associated with rollout of the feature, determine a flight state, and determine a deployment state of the feature. The flight state machine may then be configured to initiate or continue deployment of the feature in a current deployment environment or initiate deployment of the feature in a next environment based on the policy, the flight state, and the deployment state of the feature.