0
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ Thank you very much for a concise reply, already retrieved the first book you cited and it's very useful. I added some extra section to the question in case you are happy to drill down to the specifics of the "key parallels and differentiations" between the two frameworks. $\endgroup$
    – hH1sG0n3
    Nov 24, 2021 at 19:45
  • 1
    $\begingroup$ If my answer fully covers your question please mark it as such :) The additional stuff you added are wrong (at least the way they are framed). The specifics of each optimization scheme comes down to which RL method you are using. E.g. TD methods use TD error to guide learning (target value - estimated value) - and if you use function approximations you can frame it a supervised learning problem and minimize squared error between bootstrapped accumulated return and estimated return. For PGs, the PG loss can be viewed as cross entropy loss for classification problems. $\endgroup$ Nov 24, 2021 at 19:56
  • 1
    $\begingroup$ If in SL you have x as input then in RL the state is s is your input. For value methods the label y is a form of expected return. Your data will look like this {st,Rt} where Rt is expected return (and NOT reward r). For pure PGs (non Actor-Critic) your data will be (st, Rt) with Rt indicating a label. Value methods are more close to minimizing mean sq. error whereas PGs are closer to minimize cross entropy between two distributions with Rt being the label that drives learning. Note that actions ARE part of the data but I wrote it in a way similar to your formulation. $\endgroup$ Nov 24, 2021 at 20:07
1
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ It is not an opt algorithm but it is used as an optimisation framework widely in NAS (Baker et al 2017; Zoph and Le 2017; Zhong et al. 2018 etc.). Given that stochastic GD is essentially a single step of optimising model parameters given a loss, the question is about what is the hard line in differentiating the above from an state-action-reward paradigm. $\endgroup$
    – hH1sG0n3
    Nov 24, 2021 at 16:43
  • 1
    $\begingroup$ RL is an optimization scheme. As Supervised Learning solves prediction problems, RL seeks the actions at each state of a sequential task in order to optimize an utility function. Also RL in MDPs doesn't try to learn the reward or the transition functions (these aren't parameters). These functions in a basic setting are given (but they can be learned with Bayesian RL). With Value methods you learn to estimate the expected return (sum of rs) for every state (or state-action pairs) as this satisfies the Bellman equations. With Policy Gradients you optimize directly a parametrized policy function. $\endgroup$ Nov 24, 2021 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.