Reinforcement learning

 ( Markov Models ) 

$$V\_\backslash pi(s)\; =\; \backslash operatorname\; \backslash mathbb\{E\}G\backslash mid\; =\; \backslash operatorname\; \backslash mathbb\{E\}\backslash left\backslash sum\_\{t=0\}^\backslash infty,$$

where the random variable $G$ denotes the discounted return, and is defined as the sum of future discounted rewards:

$$G\; =\; \backslash sum\_\{t=0\}^\backslash infty\; \backslash gamma^t\; R\_\{t+1\}=R\_1\; +\; \backslash gamma\; R\_2\; +\; \backslash gamma^2\; R\_3\; +\; \backslash cdots,$$

where $R\_\{t+1\}$ is the reward for transitioning from state $S\_t$ to is the discount rate. $\backslash gamma$ is less than 1, so rewards in the distant future are weighted less than rewards in the immediate future.

The algorithm must find a policy with maximum expected discounted return. From the theory of Markov decision processes it is known that, without loss of generality, the search can be restricted to the set of so-called stationary policies. A policy is stationary if the action-distribution returned by it depends only on the last state visited (from the observation agent's history). The search can be further restricted to deterministic stationary policies. A deterministic stationary policy deterministically selects actions based on the current state. Since any such policy can be identified with a mapping from the set of states to the set of actions, these policies can be identified with such mappings with no loss of generality.

• For each possible policy, sample returns while following it
• Choose the policy with the largest expected discounted return

One problem with this is that the number of policies can be large, or even infinite. Another is that the variance of the returns may be large, which requires many samples to accurately estimate the discounted return of each policy.

These problems can be ameliorated if we assume some structure and allow samples generated from one policy to influence the estimates made for others. The two main approaches for achieving this are value function estimation and direct policy search.

These methods rely on the theory of Markov decision processes, where optimality is defined in a sense stronger than the one above: A policy is optimal if it achieves the best-expected discounted return from any initial state (i.e., initial distributions play no role in this definition). Again, an optimal policy can always be found among stationary policies.

To define optimality in a formal manner, define the state-value of a policy $\backslash pi$ by

$$V^\{\backslash pi\}\; (s)\; =\; \backslash operatorname\; \backslash mathbb\{E\}G\backslash mid,$$

where $G$ stands for the discounted return associated with following $\backslash pi$ from the initial state $s$. Defining $V^*(s)$ as the maximum possible state-value of $V^\backslash pi(s)$, where $\backslash pi$ is allowed to change,

$$V^*(s)\; =\; \backslash max\_\backslash pi\; V^\backslash pi(s).$$

A policy that achieves these optimal state-values in each state is called optimal. Clearly, a policy that is optimal in this sense is also optimal in the sense that it maximizes the expected discounted return, since $V^*(s)\; =\; \backslash max\_\backslash pi\; \backslash mathbb\{E\}G\backslash mid$, where $s$ is a state randomly sampled from the distribution $\backslash mu$ of initial states (so

Although state-values suffice to define optimality, it is useful to define action-values. Given a state $s$, an action $a$ and a policy $\backslash pi$, the action-value of the pair $(s,a)$ under $\backslash pi$ is defined by

$$Q^\backslash pi(s,a)\; =\; \backslash operatorname\; \backslash mathbb\{E\}G\backslash mid,$$

where $G$ now stands for the random discounted return associated with first taking action $a$ in state $s$ and following $\backslash pi$, thereafter.

The theory of Markov decision processes states that if $\backslash pi^*$ is an optimal policy, we act optimally (take the optimal action) by choosing the action from $Q^\{\backslash pi^*\}(s,\backslash cdot)$ with the highest action-value at each state, $s$. The action-value function of such an optimal policy ($Q^\{\backslash pi^*\}$) is called the optimal action-value function and is commonly denoted by $Q^*$. In summary, the knowledge of the optimal action-value function alone suffices to know how to act optimally.

Assuming full knowledge of the Markov decision process, the two basic approaches to compute the optimal action-value function are value iteration and policy iteration. Both algorithms compute a sequence of functions $Q\_k$ ($k=0,1,2,\backslash ldots$) that converge to $Q^*$. Computing these functions involves computing expectations over the whole state-space, which is impractical for all but the smallest (finite) Markov decision processes. In reinforcement learning methods, expectations are approximated by averaging over samples and using function approximation techniques to cope with the need to represent value functions over large state-action spaces.

Monte Carlo methods apply to episodic tasks, where experience is divided into episodes that eventually terminate. Policy and value function updates occur only after the completion of an episode, making these methods incremental on an episode-by-episode basis, though not on a step-by-step (online) basis. The term "Monte Carlo" generally refers to any method involving random sampling; however, in this context, it specifically refers to methods that compute averages from complete returns, rather than partial returns.

These methods function similarly to the bandit algorithms, in which returns are averaged for each state-action pair. The key difference is that actions taken in one state affect the returns of subsequent states within the same episode, making the problem non-stationary. To address this non-stationarity, Monte Carlo methods use the framework of general policy iteration (GPI). While dynamic programming computes using full knowledge of the Markov decision process, Monte Carlo methods learn these functions through sample returns. The value functions and policies interact similarly to dynamic programming to achieve optimality, first addressing the prediction problem and then extending to policy improvement and control, all based on sampled experience.

The second issue can be corrected by allowing trajectories to contribute to any state-action pair in them. This may also help to some extent with the third problem, although a better solution when returns have high variance is Sutton's temporal difference (TD) methods that are based on the recursive Bellman equation. The computation in TD methods can be incremental (when after each transition the memory is changed and the transition is thrown away), or batch (when the transitions are batched and the estimates are computed once based on the batch). Batch methods, such as the least-squares temporal difference method, may use the information in the samples better, while incremental methods are the only choice when batch methods are infeasible due to their high computational or memory complexity. Some methods try to combine the two approaches. Methods based on temporal differences also overcome the fourth issue.

Another problem specific to TD comes from their reliance on the recursive Bellman equation. Most TD methods have a so-called $\backslash lambda$ parameter $(0\backslash le\; \backslash lambda\backslash le\; 1)$ that can continuously interpolate between Monte Carlo methods that do not rely on the Bellman equations and the basic TD methods that rely entirely on the Bellman equations. This can be effective in palliating this issue.

$$Q(s,a)\; =\; \backslash sum\_\{i=1\}^d\; \backslash theta\_i\; \backslash phi\_i(s,a).$$

The algorithms then adjust the weights, instead of adjusting the values associated with the individual state-action pairs. Methods based on ideas from nonparametric statistics (which can be seen to construct their own features) have been explored.

Value iteration can also be used as a starting point, giving rise to the Q-learning algorithm and its many variants. Including Deep Q-learning methods when a neural network is used to represent Q, with various applications in stochastic search problems.

The problem with using action-values is that they may need highly precise estimates of the competing action values that can be hard to obtain when the returns are noisy, though this problem is mitigated to some extent by temporal difference methods. Using the so-called compatible function approximation method compromises generality and efficiency.

Gradient-based methods ( policy gradient methods) start with a mapping from a finite-dimensional (parameter) space to the space of policies: given the parameter vector $\backslash theta$, let $\backslash pi\_\backslash theta$ denote the policy associated to $\backslash theta$. Defining the performance function by $\backslash rho(\backslash theta)\; =\; \backslash rho^\{\backslash pi\_\backslash theta\}$ under mild conditions this function will be differentiable as a function of the parameter vector $\backslash theta$. If the gradient of $\backslash rho$ was known, one could use gradient descent. Since an analytic expression for the gradient is not available, only a noisy estimate is available. Such an estimate can be constructed in many ways, giving rise to algorithms such as Williams's REINFORCE method (which is known as the likelihood ratio method in the simulation-based optimization literature).

A large class of methods avoids relying on gradient information. These include simulated annealing, cross-entropy search or methods of evolutionary computation. Many gradient-free methods can achieve (in theory and in the limit) a global optimum.

Policy search methods may converge slowly given noisy data. For example, this happens in episodic problems when the trajectories are long and the variance of the returns is large. Value-function based methods that rely on temporal differences might help in this case. In recent years, actor–critic methods have been proposed and performed well on various problems.

Policy search methods have been used in the robotics context. Many policy search methods may get stuck in local optima (as they are based on local search).

Model-based methods can be more computationally intensive than model-free approaches, and their utility can be limited by the extent to which the Markov decision process can be learnt.

There are other ways to use models than to update a value function. For instance, in model predictive control the model is used to update the behavior directly.

Efficient exploration of Markov decision processes is given in Burnetas and Katehakis (1997). Finite-time performance bounds have also appeared for many algorithms, but these bounds are expected to be rather loose and thus more work is needed to better understand the relative advantages and limitations.

For incremental algorithms, asymptotic convergence issues have been settled. Temporal-difference-based algorithms converge under a wider set of conditions than was previously possible (for example, when used with arbitrary, smooth function approximation).

• actor-critic architecture
• actor-critic-scenery architecture
• adaptive methods that work with fewer (or no) parameters under a large number of conditions
• bug detection in software projects
• continuous learning
• combinations with logic‑based frameworks (e.g., temporal‑logic specifications, reward machines, and probabilistic argumentation).
• exploration in large Markov decision processes
• entity-based reinforcement learning
• human feedback
• interaction between implicit and explicit learning in skill acquisition
• intrinsic motivation which differentiates information-seeking, curiosity-type behaviours from task-dependent goal-directed behaviours large-scale empirical evaluations
• large (or continuous) action spaces
• modular and hierarchical reinforcement learning
  (2025). 9781510838819, Curran Associates Inc.. . ISBN 9781510838819
• multiagent/distributed reinforcement learning is a topic of interest. Applications are expanding.
• occupant-centric control
• optimization of computing resources
  (2020). 9783981926347 . ISBN 9783981926347
• partial information (e.g., using predictive state representation)
• reward function based on maximising novel information
  (2025). 9783540224846, Springer. ISBN 9783540224846
• sample-based planning (e.g., based on Monte Carlo tree search).
• securities trading
• transfer learning
• TD learning modeling dopamine-based learning in the brain. Dopaminergic projections from the substantia nigra to the basal ganglia function are the prediction error.
• value-function and policy search methods

• The algorithm can be on-policy (it performs policy updates using trajectories sampled via the current policy)cf. or off-policy.
• The action space may be discrete (e.g. the action space could be "going up", "going left", "going right", "going down", "stay") or continuous (e.g. moving the arm with a given angle).
• The state space may be discrete (e.g. the agent could be in a cell in a grid) or continuous (e.g. the agent could be located at a given position in the plane).

The self-reinforcement algorithm updates a memory matrix $W\; =\; \backslash |w(a,s)\backslash |$ such that in each iteration executes the following machine learning routine:

1. In situation $s$ perform action $a$.
2. Receive a consequence situation $s\text{'}$.
3. Compute state evaluation $v(s\text{'})$ of how good is to be in the consequence situation $s\text{'}$.
4. Update crossbar memory $w\text{'}(a,s)\; =\; w(a,s)\; +\; v(s\text{'})$.

Initial conditions of the memory are received as input from the genetic environment. It is a system with only one input (situation), and only one output (action, or behavior).

Self-reinforcement (self-learning) was introduced in 1982 along with a neural network capable of self-reinforcement learning, named Crossbar Adaptive Array (CAA).Bozinovski, S. (1982). "A self-learning system using secondary reinforcement". In Trappl, Robert (ed.). Cybernetics and Systems Research: Proceedings of the Sixth European Meeting on Cybernetics and Systems Research. North-Holland. pp. 397–402. ISBN 978-0-444-86488-8Bozinovski S. (1995) "Neuro genetic agents and structural theory of self-reinforcement learning systems". CMPSCI Technical Report 95-107, University of Massachusetts at Amherst [1] The CAA computes, in a crossbar fashion, both decisions about actions and emotions (feelings) about consequence states. The system is driven by the interaction between cognition and emotion.Bozinovski, S. (2014) "Modeling mechanisms of cognition-emotion interaction in artificial neural networks, since 1981." Procedia Computer Science p. 255–263

Early application of RL in NLP emerged in dialogue systems, where conversation was determined as a series of actions optimized for fluency and coherence. These early attempts, including policy gradient and sequence-level training techniques, laid a foundation for the broader application of reinforcement learning to other areas of NLP.

A major breakthrough happened with the introduction of Reinforcement Learning from Human Feedback (RLHF), a method in which human feedbacks are used to train a reward model that guides the RL agent. Unlike traditional rule-based or supervised systems, RLHF allows models to align their behavior with human judgments on complex and subjective tasks. This technique was initially used in the development of InstructGPT, an effective language model trained to follow human instructions and later in ChatGPT which incorporates RLHF for improving output responses and ensuring safety.

More recently, researchers have explored the use of offline RL in NLP to improve dialogue systems without the need of live human interaction. These methods optimize for user engagement, coherence, and diversity based on past conversation logs and pre-trained reward models.

• Active learning (machine learning)
• Apprenticeship learning
• Error-driven learning
• Model-free (reinforcement learning)
• Multi-agent reinforcement learning
• Optimal control
• Q-learning
• Reinforcement learning from human feedback
• State–action–reward–state–action (SARSA)
• Temporal difference learning

• (2025). 9781886529397, Athena Scientific. . ISBN 9781886529397
• (2025). 9781439821084, Taylor & Francis CRC Press. . ISBN 9781439821084
• (2025). 9789811977831, Springer Verlag, Singapore. . ISBN 9789811977831
• (2025). 9780262039246, MIT Press. . ISBN 9780262039246

• Dissecting Reinforcement Learning Series of blog post on reinforcement learning with Python code
• A (Long) Peek into Reinforcement Learning