# Learning-Based Online QoE Optimization in Multi-Agent Video Streaming
## 5 Policy Gradient for MA-Stream
### Standard RL Algorithms  
Standard RL problems consider an agent that interacts with a [PERSON] decision process \(\mathcal{M}\). The agent, at time \(t\), observes the state \(s_{t}\) of the environment and plays action \(a_{t}\) to obtain a reward \(r_{t}\), causing the environment to transition to state \(s_{t+1}\)[52]. Let the next state transition probability be \(\mathcal{P}^{a}_{ss^{\prime}}=P(s_{t+1}=s^{\prime}|s_{t}=s,a_{t}=a)\) and the expected reward of playing action \(a\) in state \(s\) be \(\mathcal{R}^{a}_{\mathcal{R}^{a}_{s}}=\mathbb{E}[r_{t}|s_{t}=s,a_{t}=a]\). The goal of the agent is to find a policy \(\pi(s,a;\theta)=P(a_{t}=a|s_{t}=s,\theta)\) parameterized on \(\theta\) that maximizes the discounted cumulative reward  
\[V_{\pi}(s_{0})=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{t}|s_{0} \right], \tag{27}\]  
where \(s_{0}\) is the initial state, and \(\gamma<1\) is a discounted factor. Using the linearity of cumulative rewards in Equation (27), the state action value function \(Q_{\pi}(s,a)\) for policy \(\pi\) is defined as  
\[Q_{\pi}(s,a)=\mathcal{R}^{a}_{s}+\gamma\sum_{s^{\prime}}\sum_{a}\mathcal{P}^{ a}_{ss^{\prime}}\pi(s,a;\theta)V_{\pi}(s^{\prime}). \tag{28}\]  
Based on Equation (28), many algorithms have been proposed, e.g., SARSA [53; 54; 55], Q-learning [23], policy gradient [24], etc. Based on these fundamental algorithms, many deep-learning-based implementations are also proposed [52].  
In many network optimization problems, the reward metrics are nonlinear when multiple subjects are jointly optimized. One typical example is resource fairness among agents/users in one network [13; 56]. With a nonlinear reward function, the decision-making engine must be aware of the historical decisions and states in the past. To demonstrate the requirement of policies that require history, we take the following example. Suppose that there are \(K=2\) users who share the network resource and we want to allocate this network resource fairly between the two users. If we use proportional fairness, the fairness for the two users can be calculated as the sum of the logarithms of the QoE indicators of the two users. We call the users 1 and 2, and we assume that both users 1 and 2 start with the same video. In slot 1, the bandwidth allocated to user 1 is higher than user 2 (\(d_{1}(1)>d_{2}(1)\)). This results in higher stall times for user 2 compared to user 1.  
Now, in the next time slot 2, user 2 switches the video with a video bitrate that is the same as the previous video, and user 1 continues with the old video. Then, since the video bitrates remain the same, allocating a higher download rate to user 2 (\(d_{2}(2)>d_{1}(1)\)) will result in lower stall times for user 2 and, hence, the fairness can be maximized. This requires the controller to ensure that the decisions at time slot 2 are made taking into account the decision made in time slot 1. However, the state defined in Section 4.1 does not store the cumulative stall duration of the previous video for the user triggering the current time slot. The algorithm used in this paper to deal with such a nonlinear problem is explained in the next subsection.  
We further note that one possible way to tackle the non-Markovian nature is to introduce a high-order Markov model by including the objective value until time slot \(l-1\) in the state. This approach, however, potentially increases the state space dramatically to \(\left(SA\right)^{L}\), where \(S\) is the number of states and \(A\) is the number of actions that the controller can take. Hence, we consider a multi-agent learning algorithm in the next session, which does not require the use of high-order Markov models and allows an individual agent to improve its policy.