Customers accessing resources or services in a distributed environment can obtain assurance that a provider of that environment will only allow requests to access those resources or services when those requests satisfy at least one security policy associated with the customer. A customer can provide a security policy update that might be written in a different representation (e.g., version) than is supported by all relevant policy evaluation engines across the distributed environment. A component or service such as an access management service can evaluate the representation of the policy, as well as the representations supported by the evaluation engines, and can determine if the features of the policy update are supported by the representations of the engines. If so, the policy update can be translated to express the policy document in the supported representation(s), such that the policy can be utilized without having to update the relevant engines.