For storing avatars in s3, which approach has the lowest cost?
For the best performance naming many small files in an s3 bucket may not be the best idea unless they user_id is a random string. See how the S3 hashing algorithm works https://aws.amazon.com/blogs/aws/amazon-s3-performance-tips-tricks-seattle-hiring-event/

So replacing it by a random hashed value may not be that bad. Of course you need to store the hash in the user profile or you need to calculate it from something. If you add something like profile id or last changed timestamp you can do sha1/md5 of (userid+lastchanged) and if you update timestamp you has the hash of the current avatar. 

The older one you can simply delete. CloudFront will remove it from its cache after expiration https://docs.aws.amazon.com/AmazonCloudFront/latest/DeveloperGuide/Expiration.html

This will more complex algorithm, but if the costs are the concern, a little bit of extra work seems to be a reasonable approach. Not sure how do you handle the uploads, but it may be a good opportunity to play a bit with step functions which would make sure that the new avatar is uploaded correctly and then the old one is removed as well. 

It's kind of a programming question, but I get your point - it is very specific to AWS environment and requires a particular knowledge about how the infrastructure works.