# Deep-Reinforcement-Learning-Based Planner for City Tours for Cruise Passengers +
## 3 Reinforcement Learning Background  
Reinforcement learning (RL) is a powerful machine-learning technique to solve problems involving sequential decision-making. In RL, an artificial agent, a controller, interacts with an uncertain environment to maximize long-term rewards. The agent learns an optimal policy by selecting and executing actions that lead to state transitions and influence the environment. Each state transition is associated with a numerical reward, which can be positive or negative. RL provides a framework for training agents to achieve goals through interactions with their environment. The concept of RL is extensively discussed in the book _\"Reinforcement Learning\"_ by [21]. The agent's primary objective in reinforcement learning is maximizing the cumulative rewards it receives. The agent achieves this by following a policy consisting of stimulus-response rules, mapping each environment state to a set of possible actions. The policy can be implemented using a lookup table or more complex computations such as search processes. The policy guides the agent's decision-making process and ensures the system's proper functioning. However, a major challenge in RL is that the agent often interacts with an environment with considerable uncertainty. This uncertainty relates to the changes in the state of the environment and the rewards associated with those state transitions. The agent must navigate this uncertain environment to learn and make optimal decisions that lead to the highest possible rewards. In the context of reinforcement learning, an RL task is formally defined as a Markov decision process (MDP). The MDP is represented as a tuple, \(\langle S,A,R,P,\gamma\rangle\), where \(S\) is a finite set of states, \(A\) is a finite set of actions, \(R\) is a reward function, \(P\) represents the state transition probability, and \(\gamma\) is a discount factor, which ranges between 0 and 1. The Markov property assumes that the future state depends solely on the current state and is independent of previous states. The MDP describes the dynamics of the environment, specifying the available actions, the possible states, and the transition probabilities. For any given state-action pair \((s,a)\), the probability of transitioning to a particular next state and receiving a reward is denoted as \(p(s^{\prime},r|s,a)\). This probability captures the stochastic nature of the environment. In the context of RL, the objective is to maximize the cumulative sum of rewards from a given time step \(t\) to the final time step \(T\), denoted as \(G_{t}=R_{t+1}+R_{t+2}+\ldots+R_{T}\). The goal is to find the optimal policy that maximizes this cumulative reward. Often, such a function is referred to as a _discounted return_:  
\[G_{t}=\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1} \tag{1}\]  
where \(0\leq\gamma\leq 1\) is the _discount rate_ enabling a trade-off between two needs, the attempt to achieve the maximum cumulative reward and the desire to gain a sufficient benefit within a reasonable time. A policy \(\pi\) is a probability distribution over actions and states. \[\pi(a|s)\doteq P\big{[}A_{t}=a|S_{t}=s\big{]} \tag{2}\]  
Given the policy  
The optimal action-value function \(q_{*}(s,a)\) is defined as the maximum value function of all policies, and it is the one that allows the highest return reward to be achieved:  
\[q_{*}(s,a)=\max_{\pi}q_{\pi}(s,a),\forall s\in S \tag{4}\]  
Q-learning is a commonly used algorithm to determine the optimal action-value function, denoted as \(q_{*}\). It utilizes a two-dimensional array known as a Q-table, which stores information about state-action pairs. Each cell (i, j) in the Q-table represents the estimated value, denoted as q(i, j), that can be achieved by selecting action j in state i. During the learning process, the Q-table is updated iteratively based on the agent's interactions with the environment. The agent explores different actions, observes the resulting rewards and next states, and updates the corresponding Q-values in the table accordingly.