## 4 The Model of Packet Size Adaptation Using Bounded Multi-Armed Bandits
### Uniform Exploration and Bounded Knapsack-Based Exploitation
#### 4.3.2 The Exploitation Stage of the Bounded Knapsack  
In the section, we mainly introduce the development phase bounded \(\varepsilon\)-first algorithm. To do that, we first introduce the bounded knapsack problem that forms the basis of this phase of the method applied. Then, an efficient approximate way to solve the knapsack-based problem that used in the development state is introduced.The bounded knapsack-based problem is modeled as follows. In case of N types of elements, each type i has a length value \(v_{i}\), and weight \(w_{i}\). In another way, there is also a knapsack-based with capacity of weight C. A bounded knapsack-based problem selecting the type of integer unit knapsack to maximize the total value of goods, the total weight of such elements is no more than the capacity of the knapsack weight, but each element i can't be selected not limited to \(L_{i}\) times. Because the goal is to find the non-negative integers \(x_{1},x_{2},x_{3},\cdots,x_{n},\cdots\), that:  
\[\max\sum_{i=1}^{N}x_{i}v_{i}\ \ s.t.\sum_{i=1}^{N}x_{i}v_{i}\leq C,\forall i0\leq x _{i}\leq L_{i} \tag{23}\]  
It is important to set each set \(L_{i}=1\) then we obtain the standard model based on 0-1 knapsack. Because the limited of the knapsack is a typical NP-hard problem, the optimal solution method does not guarantee a lower cost. However, approximate optimal ways have been used to solve the problem, for example, a bounded greed algorithm. We use a simple effective approximation bounded greedy algorithm, whose computational complexity is O(NlogN) where N is the number of types. This selection reason is that it is used in addition to the efficiency of the theoretical analysis. The working principle of the bounded greedy algorithm is as follows: Let \(\overset{v_{i}}{\underset{w_{i}}{\overset{\text{}}{\right. }}}\) denote the density. In the early stages, we classify the item types by reducing the density. The computational complexity is O(NlogN). In the first round of the algorithm, we determine the highest density of the item type. In the capacity of no more than a knapsack or item limit \(L_{i}\), we select a viable item as more units. After that, we identify with the rest of the feasible elements which are still suitable for the remaining capacity of the knapsack. When it do not exceed the residual capacity of knapsack or the corresponding item, once again we choose as many units as is feasible. We do this step again and again, until no feasible project is left. Obviously, N is the maximum number of rounds. This algorithm is chosen because it can effectively use the theoretical analysis. Now, we use the bounded knapsack problem to reduce the exploitation stage of the task assignment problem. Let \(\overset{\hphantom{\text{}}\hphantom{\text{}}}{\mu}\) represent the estimate value of \(\mu\) after the exploration stage. The expected value should be calculated by the average samples of the received return of machine arm i. Given this, our goal is to settle the following integer problem:Sensors_**2015**, _15_  
\[ \begin{split}\max\sum_{i=1}^{N}\overset{\wedge}{\mu}x_{i}^{explot}& s.t.\sum_{i=1}^{N}c_{i}x_{i}^{explot}\leq(1-\varepsilon)B,\\ &\forall i;0\leq x_{i}^{explot}\leq L_{i}-x_{i}^{explore}\end{split}  \tag{24}\]  
where \(x_{i}^{explot}\) is the decision variable. It represents the times arm i is drawn in the exploitation stage. In order to settle the problem, we apply the abovementioned bounded greedy algorithm. With every \(x_{i}^{explot}\) value, the following exploitation algorithm is used now: In each time slot, if drawing arm i, and the number of times is no more than \(x_{i}^{explot}\), we draw that arm at t time step. The pseudo code of the algorithm is described in Algorithm 1. ```
1:Exploration stage:
2: t = 1; \(B^{expl}=\varepsilon B\)
3:while drawing is feasible do
4: draw each arm;
5: \(B_{i,1}^{expl}=\varepsilon B_{i}^{expl}-\sum_{i\prec c_{i}}^{N};\) t = t + 1;
6:endwhile
7:while pulling is feasible do
8:if\(B_{i}^{expl}<\min_{i}c_{i}\)then
9: STOP!