# A Survey of Planning and Learning in Games
## 3 Learning in Games
### Learning Techniques
#### 3.1.4 Reinforcement Learning  
Reinforcement learning is a subfield of ML concerned with the design of agents that learn through trial and error by interacting with their operating environment [95]. Formally, the RL task is formalized as a Markov decision process (MDP) defined as a 4-tuple \((S,\,A,\,P,\,R)\), where \(S\) denotes a set of states (i.e., state space), \(A\) denotes a set of actions (i.e., action space), \(P(s_{t+1}|s_{t},\,a_{t})\) represents the state transition probabilities (i.e., the probability of transitioning from state \(s_{t}\in S\) to state \(s_{t+1}\in S\) when action \(a_{t}\in A\) is performed at time \(t\)), and \(R(s,a)\) denotes the reward function (i.e., the immediate reward from taking action \(a\in A\) in state \(s\in S\)). Figure 4 depicts the interaction between the agent and the environment in an MDP. The objective of RL is to find a policy \(\pi\) (i.e., a mapping between states and actions), defined as \(\pi\,:S\times A\rightarrow[0,1]\) if the policy is stochastic or as \(\pi\,:S\to a\in A(s)\) if the policy is deterministic. The objective of this policy is to maximize the (discounted) return \(G_{t}=\sum_{k=0}^{\infty}\gamma^{k}r_{t+k}\) over time. \(0\leq\gamma\leq 1\) is the discount rate and \(A(s)\) denotes the set of possible actions in state \(s\). In RL, \(\pi\) can be derived via two different approaches: value function and policy gradient. In the value function approach, two different value functions are learned: the state-value function \(V^{\pi}(s)=\mathbb{E}_{\pi}\Big{[}\sum_{k=0}^{\infty}\gamma^{k}r_{t+k}|s_{t}=s \Big{]}\), which computes the expected return when starting in state and following \(\pi\) thereafter (i.e., the value of the state), and the action-value function \(Q^{\pi}(s,a)=\mathbb{E}_{\pi}\Big{[}\sum_{k=0}^{\infty}\gamma^{k}r_{t+k}|s_{t }=s,a_{t}=a\Big{]}\), which computes the expected return when starting in state \(s\), taking action \(a\) and following \(\pi\) thereafter (i.e., the value of taking an action in a specific state). \(\mathbb{E}\) denotes expectation. These functions can then be used to derive \(\pi\), e.g., \(\pi(s)=\text{argmax}_{a}Q^{\pi}(s,a)\). In problems with large state spaces, such as games, these functions are usually approximated using NNs, in which case RL is also referred to as deep RL (DRL). Policy gradient methods on the other hand approximate \(\pi\) directly. Figure 4: The agent-environment interaction in a Markov decision process (MDP). The agent and the environment interact over a sequence of discrete time steps \(t=0,\,1,\,2,\,\dots\). At each time step \(t\) the agent receives a representation of the state of the environment at that time step \(s_{t}\) and performs an action \(a_{t}\). In response to the action of the agent the environment transitions to the next state \(s_{t+1}\). At the next time step \(t+1\) the agent receives a numerical value (or reward) \(r_{t+1}\) assessing its performance and uses this information together with the current state \(s_{t+1}\) to choose its next action \(a_{t+1}\). Finally, RL methods are catalogued as model-based or model-free, depending respectively on whether they use a model of the environment or not. Q-Learning [96; 97] is a well-known example of a model-free RL algorithm. Q-Learning belongs to the family of TD learning (TDL) methods and estimates the Q-values as \(Q(s_{t},a_{t})=Q(s_{t},a_{t})+\alpha[r_{t}+\gamma\underset{b}{\text{max}}Q(s_{t+1 },b)-Q(s_{t},a_{t})]\), where \(\alpha\) is the learning rate and \(\delta_{t}=r_{t}+\gamma\underset{b}{\text{max}}Q(s_{t+1},b)-Q(s_{t},a_{t})\) refers to the temporal error. Value Iteration (VI) is a well-known model-based RL algorithm. Model-based RL algorithms can also be thought of as planning algorithms, since they use a model of the environment to simulate actions in order to learn their long-term consequences. Model-based RL is further discussed in Section 5.2.1. Refer to [95] for an in-depth introduction to RL.