Is reinforcement learning analogous to stochastic gradient descent?

Question

Not in a strict mathematical formulation sense but, would there be there any key overlapping principals for the two optimisation approaches?

For example, how does $$\{x_i, y_i, \mathrm{grad}_i \}$$ (for feature, label and respective gradient from training example of SGD) defer from $$\{s_i, a_i, r_i\}$$ for state, action and reward example for RL? Given that $x_i$ can be viewed as a state, label $y_i$ as a reward (e.g. good/bad label) and $\mathrm{grad}_i$ as action.

I appreciate that reinforcement learning is (a) learning what to do and how to map situations to actions as well as (b) learning from interaction and how in such a setting it is impractical to acquire "supervised training" training examples from all possible set of actions/rewards. But in essence, I would like to see whether there is a clear differentiation between the two abstractions above.

Answer 1

From your question I assume that you are familiar with at least basic concepts in RL so I won't dive into too many details. RL in general is not SGD. In RL you will encounter various optimization schemes in order to optimize an utility function. Two of the most popular families of methods used for optimizing an utility function (in RL MDP formulation) are Value methods and Policy Gradient methods.

• Value (or Critic) Methods
  • Model-based value methods use Dynamic Programming (DP) to optimize an utility function. In simple wording, once optimal value functions have been found, that satisfy the Bellman Optimality Equations, can be used to obtain optimal policies.
  • Model-free value methods use a form of Temporal Difference (TD) Learning to estimate the value function. TDs are a combination of DP and Monte Carlo (MC) methods. Like DP, TD methods update estimates based in part on other learned estimates, without waiting for a final outcome (they bootstrap). Like MC methods, TD methods can learn directly from raw experience without a model of the task’s dynamics. A very common TD algorithm is Q-learning. It has been proved that, under the assumption of infinite visitations of every state-action pair, Q-learning converges to the optimal value function.
• Policy Gradient Methods (or Actor Methods)

  • PG methods assume a parametrized policy function and use gradient ascent to optimize its parameters in order to maximize expected return: $$\theta_{h+1}=\theta_{h}+\left.\alpha_{h} \nabla_{\theta} J\right|_{\theta=\theta_{h}}$$

  • In this case you could possibly state that RL is following the steepest descent on the expected return.

I post some great references in case you would like to delve into the details:

1. Reinforcement Learning: An Introduction, 2nd edition
2. Policy Gradient Methods
3. Policy Optimization
4. Policy Gradient Algorithms

Answer 2

Reinforcement Learning is not an optimization algorithm (which stochastic gradient descent is).

Stochastic Gradient Descent is an optimization algorithm which seeks to minimize a given target/objective function. Reinforcement learning does nothing of that sort.

Reinforcement Learning is essentially learning the parameters of a Markov Decision Process (MDP). Parameters are - reward we get for being in a particular state (can be any real number, with a negative reward acting as a penalty), and the probability of transition from one state to another when taking a particular action.

Once we have the parameters of an MDP choosing the best policy (best action to take for a given state for the situation) is essentially a solved problem (a closed form formula exists).