In one embodiment, a method includes accessing policy states associated with a policy, determining that a particular policy state of the policy states should not be pruned, and generating possible next policy states for the particular policy state based on one or more policy actions and one or more costs associated with the respective policy actions, wherein each policy action is associated with one or more probabilities corresponding to one or more possibilities of resulting in one or more of the possible next policy states, wherein the respective cost associated with the policy action is determined based on one or more computing costs of the policy action resulting in the one or more of the possible next policy states in combination with the respective one or more probabilities, and wherein each policy state of the created policy evaluation tree comprises a rule state for each rule of the policy.