AWS API Gateway: User anonymous is not authorized to execute API

Even if the Authorization is set to NONE for your OPTIONS method, it will check the resource policy if you have one.

You can make your OPTIONS method public available by setting the following API gateway resource policy.

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Effect": "Allow",
            "Principal": {
                "AWS": "*"
            },
            "Action": "execute-api:Invoke",
            "Resource": "arn:aws:execute-api:{REGION}:{AWS_ACCOUNT}:{YOUR_API_ID}/{YOUR_API_STAGE}/OPTIONS/*"
        }
    ]
}

Ckeck How API Gateway Resource Policies Affect Authorization Workflow

Something that tripped me up: "If the API has been deployed previously in the API Gateway console, you'll need to redeploy it for the resource policy to take effect."

https://docs.aws.amazon.com/apigateway/latest/developerguide/apigateway-resource-policies-create-attach.html