According to Roy Fielding's Hypermedia As The Engine of Application State (HATEOAS), each resource should be accompagnied with a list of actions (or links) that can be done on that resource.
If the actions are included in the entity (as apposed to using the links attribute of Json-Schema), how do I tell the user-agent that a specific option is not available to the authenticated user?
The backend could do the filtering, but then the same resource URL could have different representations depending on the authenticated user. And this does not seem REST-friendly or caching friendly.
The other option is to leave all links, and let the user-agent receive a 403 Forbidden when the action is not available to the authenticated user. This can be annoying to the user.
How to inform the user-agent on the available actions when those can change depending on the authenticated user, while remaining REST-friendly?
You are correct. Creating representations that vary based on user permission is not particularly cache friendly. Is it possible to classify permission variants into just a few categories? e.g. resource-low-security, resource-medium-security resource-high-security
Sometimes this approach is possible, sometimes it is not. The other aspect to consider is whether caching is critical for this particular resource. Maybe it is now?
Also, it is not necessary to wait until the user clicks on a link to find out if the user has the permissions to follow it. The client could perform an OPTIONS request on links in the background to discover which links are available and dynamically disable the links that are not accessible.
There is no single answer to this problem. Different solutions will work in different cases depending on the requirements.