# How do I represent sample efficiency of RL rewards in mathematical notation?

I define sample efficiency as the area under the curve/graph, where $$x$$-axis is the number of episodes while y-axis is the cumulative reward for that episode. I would like to formally define it with a mathematical function.

If the notation for cumulative reward for $$x$$th episode is:

$$R_x = \sum_{t=0}^{t=T} r_t,$$

where $$r_t$$ is the reward for timestep $$t$$ and $$T$$ is the max number if steps per episode.

So is the equation for area under the graph/curve the one below?

$$\text{Sample Efficiency} =\int_{a}^{b} R_x \ dx$$

I will be just using a Python library to get the area under the graph which uses Simpson's rule for integrating.

Episodes are discrete, there is no need for calculus. Your "sample efficiency" metric is:

$$\sum_{x=a}^b R_x$$

The quantity you are measuring per episode is the return (undiscounted). The sum of this over many episodes does not measure sample efficiency as the term is usually meant, although the sample efficiency of the algorithm you use should impact the numbers you see. Getting a high value of this metric, averaged over many training runs, implies two things:

• The algorithm learns to exploit the environment quickly. This is related to sample efficiency.

• The algorithm does not pay a high cost for exploring. This is not directly related to sample efficiency, and may in fact be in conflict with learning an environment quickly.

These are both desirable properties of a reinforcement learning algorithm. They often need to be considered in balance, this is the exploration versus exploitation dilemma in RL, which can be studied in a simplified form in mult-arm bandit problems. You may be able to take inspiration from how bandit algorithms are measured for other metrics related to efficient learning.

Your metric is most useful when considering learning agents run in a live environment, where costs of mistakes during learning are real.

If instead you are training an agent in a safe environment - e.g. in simulation - then you may not be interested in the undiscounted returns $$R_x$$ during training. Your goal may be to train the agent using the least CPU time, the least number of simulation runs etc. In which case, you care most about the mean return achievable by the trained algorithm after spending a certain amount of whatever resource you are managing. This is more closely related to the concept of sample efficiency, and to measure that you could plot the returns from separate test episodes at routine intervals, with exploration removed (e.g. if you were using DQN, then with $$\epsilon = 0$$

• Thanks for this. I am using policy gradient algorithms like SAC and TD3 for continuous action space. Episode has NO terminal state so all episodes are of the same length. Which sample efficiency metric do you think I'd use? And yes, I am using a simulation Jun 28 at 16:45
• I would use a metric of minimising the resource spend that I am most concerned about, whilst reaching either acceptable, near optimal or optimal behaviour, averaged over enough runs that differences between approaches can be shown to be significant. So if you are truly interested only in number of simulated time steps required (a fairly pure measure of sample efficiency), then count the number of simulated time steps required to reach some close-to-optimal mean reward per time step. Jun 28 at 19:24