Student Member, IEEE Zhou Liang

Member, IEEE Baoyu Zheng

Anne Wei

Benoît Geller

Jingwu Cui

L Zhou

A Robust Resolution-Enhancement Scheme for Video Transmission over Mobile Ad-Hoc Networks

Keywords: error-resilient, super-resolution, mobile ad-hoc networks, resolution-enhancement

Historically, Error-Resilient (ER) video transmission and Super-Resolution (SR) image reconstruction techniques have evolved separately. In this paper, we propose a coordinated application of ER and SR to enhance the resolution of image transmitted over mobile ad-hoc networks. In order to combat error propagation, a flexible multiple description coding method based on shifted 3-D SPIHT ( 3-D Set Partitioning In Hierarchical Trees) algorithm is presented to generate variable independent descriptions (substreams) according to the network condition. And then, a novel unequal error protection strategy based on the priority level is provided to assign a higher level of error protection to more important parts of bitstream. Moreover, a robust SR algorithm is proposed in the presence of different kinds of packet loss rate to enhance the image resolution. Experimental results indicate that the proposed robust resolution-enhancement scheme outperforms the competing methods from the aspects of PSNR (Peak-Signal-to-Noise Ratio) and visual quality under different packet loss rates.

I. INTRODUCTION

In recent years, mobile ad-hoc networks (MANETs) has emerged as one of the high growth applications of wireless communication technology, and the interest in the transmission of video over MANETs has increased dramatically. However, this error-prone network is packet based where many potential reasons may result in packet loss which has a devastating effect on the visual quality of images at the receiver. Furthermore, in most electronic imaging applications, image with high resolution (HR) is desired and often required because HR image can offer more details that may be critical in various applications. Unfortunately, it is challenging to provide HR image transmitted over MANETs where no Quality of Service (QoS) is guaranteed at the network level. In order for HR, it would be essential to solve the following primary technical challenges:

• Trade-off between coding efficiency and error resilience. Most current standardized video codecs, including MPEG-2/4 and H.263/4 are designed to achieve high compression efficiency at the expense of error resilience. The coding efficiency in these codecs is achieved by using motion-compensated prediction to reduce the temporal and statistical redundancy between the video frames. This brings a severe problem, namely error propagation, where errors due to packet loss in a reference frame propagate to all of the dependent frames leading to visual artifacts that can be long lasting and annoying [START_REF] Kung | Spatial and temporal error concealment techniques for video transmission over noisy channels[END_REF].

Therefore, Error resilience is needed to achieve robust video transmission. One strategy to achieve resilience is to insert redundant information systematically into compressed video signals so that the decoder can compensate transmission errors. The redundant information can be error correction codes [START_REF] Hwang | Layered video coding based on displaced frame difference prediction and multi-resolution block matching[END_REF], [START_REF] Mathew | Efficient layered video coding using data partitioning[END_REF] or multiple descriptions [START_REF] Kim | Multiple description coding of motion fields for robust video transmission[END_REF], [START_REF] Wang | Error-resilient video coding using multiple description motion compensation[END_REF]. The former one combined with layered coding can provide good performance in prioritized networks while the latter is suitable for delivery over multiple channels to enhance reliability. However, error resilience is achieved at the expense of coding efficiency in both methods. Another way can be achieved with feedback mechanism to request retransmission or adjust encoding modes according to conditions. The methods proposed in [START_REF] Zhang | Video coding with optimal inter/intra-mode switching for packet loss resilience[END_REF], [START_REF] Steinbach | Standard compatible extension of H.263 for robust video transmission in mobile environment[END_REF] rely on feedback from the decoder and are, therefore, applicationlimited.

• Enhance resolution under the scenario of packet loss. In order for HR image, one promising approach, which is called super resolution (SR), uses signal processing techniques to obtain a HR image from observed multiple low resolution (LR) images [START_REF] Park | Super-Resolution Image Reconstruction: A Technical Overview[END_REF]. In the past few decades, a variety of SR methods have been proposed for estimating the HR image from a set of LR images without taking into account the packet loss during the transmission. The critical requirement for traditional SR approach is that the observations contain different but related views of the scene [START_REF] Park | Super-Resolution Image Reconstruction: A Technical Overview[END_REF], however, it can not be guaranteed under the framework of error-prone networks where the packet loss destroys the correlation between the related views of scene. Therefore, how to apply the SR approach to the packet loss scenario is still an open problem. Here, it is necessary to differentiate error concealment (EC) with SR. EC hides or recovers the errors by using correctly received image information without modifying source or channel coding schemes [START_REF] Lie | Video Error Concealment by Integrating Greedy suboptimization and Kalman Filtering Techniques[END_REF], which can only produce a visually acceptable (rather than exact) image from the available data, and can not enhance the physical resolution of the image. While SR extracts the exact detail information hidden among the different but related video frames to enhance the image resolution.

To meet these challenges, in this paper, we propose an entire scheme to get HR video transmitted over MANETs by integrating efficient ER strategy with robust SR algorithm, which not only provides relatively efficient compression and transport performance but also provides robust resolution-enhancement performance in the presence of various packet loss rates. An outline of the remainder of this paper is as follows. In section II, we describe the whole system and provide the related technique preliminaries used in this work; in section III, we present an adaptive error-resilient strategy to reduce the distortion due to the packet loss; and then, a robust SR algorithm to enhance the resolution of received image is proposed in section IV; section V provides the simulation results and compares the performance of the proposed scheme with other comparison systems. Finally, we give some concluding remarks.

II. PRELIMINARIES

In this section, we first overview system framework of the video transmission and processing, and then present some related technical preliminaries used in this work, such as shifted 3-D SPIHT algorithm and multiple description coding.

A. System Overview

The total architecture of video transmission and processing illustrated in Fig. 1 is composed of three processes, such as image degradation, image transmission over error-prone networks and Generally, all of the video sequences we observe are LR images comparing to the real-world scenes which are viewed as the original HR images. That is because the degradation process affects the quality of images acquired by digital video camera which results from the lens' physical limits, such as motion warping, optical blur and additive noise. In addition, these LR images are usually down-sampled convenient for transmission or storage. Next, the observed LR images are encoded and packetized preparing for transmission over error-prone networks. In this paper, the method of encoding and packetizing is based on the shifted 3-D SPIHT algorithm to generate variable descriptions (substreams) at the sender, and different descriptions employ different error protection strategies according to its priority. As to the MANETs system, suppose that there are n mobile nodes in the system and n (1 ≤ n < n)senders (sources) stream complementary substreams to a single receiver (destination) over different paths. In this system, sender-n streams substreams-n to the receiver over path-n (n = 1, 2..., n ).At the receiver, the received images can be reconstructed after depacketizing and decoding the received data.

B. Shifted 3-D SPIHT Algorithm

Wavelet zero-tree image-coding technique was first addressed by Shapiro [START_REF] Shapiro | Embedded image coding using zerotrees of wavelet coefficient[END_REF], and further developed by Said and Pearlman [START_REF] Said | A New, fast and efficient image codec based on set partitioning in hierarchical trees[END_REF], and have provided unprecedented high performance in image compression with low complexity. Later, extended 2-D zero-tree wavelet coding (EZW) by [START_REF] Said | A New, fast and efficient image codec based on set partitioning in hierarchical trees[END_REF] had been introduced to three dimensions (3-D EZW) by Chen and Pearlman [START_REF] Chen | Three-dimensional subband coding of video using the zero-tree method[END_REF], and had shown promise of an effective and computationally simple video-coding system without motion compensation, obtaining excellent visual results. And then, Kim and Pearlman developed the 3-D SPIHT [START_REF] Kim | An embedded wavelet video coder using three-dimensional set partitioning in hierarchical trees[END_REF] coding algorithm based on the 3-D EZW mentioned in [START_REF] Chen | Three-dimensional subband coding of video using the zero-tree method[END_REF].

3-D SPIHT algorithm provides excellent rate-distortion performance along with a low encoding complexity, and spatiotemporal trees are defined as groups of wavelet transform coefficients organized into trees rooted in the lowest frequency subband and the spatially and temporally related coefficients in the higher frequency subbands, which is helpful to reduce the error propagation [START_REF] Kim | An embedded wavelet video coder using three-dimensional set partitioning in hierarchical trees[END_REF]. Fig. 2(a) shows how coefficients in a 3-D transform are related according to their spatial and temporal domains. The parent-children linkage except at the highest and lowest pyramid levels (which do not have offspring) is:

O(i, j, k) = {(2i,
where O(i, j, k) represents a 3-D of coordinates of all the offspring at node (i, j, k).

Although the SPIHT-coded bitstream has many advantages, it is also sensitive to data losses because of the dependence among wavelet coefficients in constructing a significance map.

Motivated by the packetized 2-D SPIHT coding algorithm [START_REF] Sriraja | A packetized SPIHT algorithm with over complete wavelet coefficients for increased robustness[END_REF] partitions the wavelet coefficients into independent packets to combat error propagation by shifting 2-D wavelet tree structure, here we apply it to 3-D case by shifting the 3-D wavelet tree structure. The essential aim is the wavelet coefficients from different sub-bands are interleaved to form independent packets that can be decoded independently. The formation of the shifted wavelet trees is shown in Fig. 2(b). It should be noted that although a lot of multi-interlaced partitioning and packetizing methods have been presented in recent years [START_REF] Bajic | Domain-based multiple description coding of images and video[END_REF], they could enhance the encoding burden greatly. Therefore, we don't employ them here.

C. Multiple Description Coding

As to the way to protect data from packet losses induced by the error-prone channels, one of the most common ways is to add the redundant information at the bitstream so that the original video can be recovered in presence of the packet loss, and the code should be devised in such a way that the decoder is able to recover the lost information or conceal the irrecoverable errors.

One such popular approach is multiple description coding (MDC), which is similar in spirit to the multiple-substream approach. The fundamental principle of MDC is to generate multiple correlated descriptions of the source such that each description approximates the source with a certain level of fidelity [START_REF] Kim | Distributed Video Streaming Using Multiple Description Coding and Unequal Error Protection[END_REF]. MDC does not impose any dependency among its descriptions so that each extra successfully received description improves the quality further regardless of what has been received so far.

The benefits of using MDC in video streaming can be further amplified when MDC is combined with path diversity (PD) [START_REF] Gogate | Supporting image and video applications in a multihop radio environment using path diversity and multiple description coding[END_REF]. In this approach, each substream (or description) is explicitly transmitted over an independent path to receiver. PD exploits the fact that the probability of having all the paths simultaneously congested is relatively low. As a result, the use of PD in video streaming can achieve higher throughput and increase tolerance to packet loss.

III. ADAPTIVE ERROR-RESILIENT STRATEGY

In this section, a novel error-resilient strategy is proposed based on partitioning the GOF (group of frames) into variable substreams with different priority levels adapting to the current network condition.

A. Unequal Error Protection

Progressive bitstreams provide a natural basis for unequal error protection (UEP), by which perceptually more important parts of the bitstream are assigned a greater level of error protection [START_REF] Mohr | Unequal loss protection: Graceful degradation of image quality over packet erasure channel through forward error correction[END_REF]. In this work, we propose a novel UEP based on the expected lifetime of the path to guarantee the important part (high priority) of substreams are received at the receiver. That is to say, important substream corresponds to the "good" path.

Here, we set the priority of the substreams according to the importance of the subband derived from the wavelet decomposition.In general, the LL k provides more visual information than HH k ,HL k and LH k (where k denotes the decomposition level),so we set priority level of LL k as 2 2k ,while the other three subbands are 2 2(k-1) . To the priority of path, we use the ratio of remaining energy (E) to transmit power (P T ) to denote the expected lifetime of the node. So the higher the ratio is the more lifetimes of the node. In order to maximize the lifetime of the whole network system, to an arbitrary node i, the criterion of its next hop should satisfy that

R(i) = max(E i /P T i ) (2)
where R(i) denotes the maximum expected lifetime for node i corresponding to the optimal energy transmission to next hop which locates on the desired path. Assuming that the discovered path j consists of nodes such as i, i + 1, ...i + n (n ∈ N + ) , R j , the energy consumer function of path j, here we define

R j = min{R(i), R(i + 1), ...R(i + n)} (3)
This means that the minimum expected lifetime of each node determines the whole lifetime of the path. Because once one of the nodes in the path dies, the whole path dies as well. The more R j the higher priority of the path, and correspond to higher level of encoded substream. Note that, in order to realize the proposed UEP, we modify the traditional DSR (Dynamic Source Routing) Protocol as follows: besides adding the node's ID to the request packet, each node also adds the information of transmit power and remaining energy to the request packet, if the node receives packet, the information of the received power is also added to the packet. So when the sender node receives the request packet, the packet should consist of the route nodes' ID, the remaining energy of each route node and each node's transmit power and received power.

B. Flexible MDC

We focus on how to design the MDC according to the networking condition: one is how many descriptions are needed to guarantee the reconstructed video quality as well as keep the total bitstream as little as possible, while the other one is how to distribute these encoded data to the determinate substreams.

Obviously, the more substream the more data received at the destination, but it is infeasible for the practical wireless network. Here, we give an oversimplified method to compute the minimum needed substream number according to the packet loss rate (P L ) of the obtained channels.

With regard to the channel model, we use a two-state Markov model (i.e. Gilbert model) to simulate the bursty packet loss behavior [START_REF] Horn | Robust internet video transmission based on scalable coding and unequal error protection[END_REF]. The two states of this model are denoted as G (good) and B (bad). In state G, packets are received correctly and timely, whereas, in state B, packets are assumed to be lost. This model can be described by the transition probabilities p from state G to B and q from state B to G. Then the average P L is given by

P L = p p + q (4)
And the average length of burst errors L B is given by

L B = 1 p (5)
So the average channel P L of path j is p j /p j + q j . Suppose that all the transmit probability of potential paths are independent, the minimum number of substreams L is

min L∈N + L j=1 ( p j p j + q j ) ≤ T hr (6)
where T hr is the tolerance P L threshold which depends on the practical application requirements.

Usually, its value varies from 10 -1 ∼ 10 -4 [START_REF] Kang | Transmission of Multiple Description Codes Over Wireless Channels Using Channel Balancing[END_REF], in this paper, we set T hr = 10 -2 .

In the case of data distribution, it also contains two aspects: one is the decision of the wavelet decomposition level, and the other one is the data distribution among these determinate paths.

As to this point, we employ three basic principles:

• High priority level of the source data corresponding to high priority of the path, which is called equity principle.

• The whole transmission system only guarantees the most important source data, which has the highest priority level.

• As to other parts of the data, we use the best-effort strategy to transmit.

If a K-level dyadic wavelet decomposition is used, the number of wavelet coefficients in the k

(0 < k ≤ K) level spatial-frequency subband C ∈ {LL, LH, HL, HH} is given by C k = ( X 2 k ) × ( Y 2 k ) (7)
where X and Y represent the frame width and height respectively. The level of the wavelet decomposition is decided by the expected lifetime of the highest priority path R H . The essential requirement is that the GOF of the most important data should be guaranteed to transmit from source to destination over the highest priority path, so

min K≥1 (LL K /XY ) × r b × N GOF F × S ≤ R H ( 8
)
where LL K /XY denotes the ratio of the most important part in the total data streaming; N GOF is the frame number of one GOF; r b is the total source coding rate in bytes/s; F is the frame rate in frames/s; S is the packet size in bytes.

The fundamental distribution rule of data distribution is that the highest priority level data should be distributed at the each path while the others only distributed once at the path. Assuming C ∈ {LH, HL, HH}, and expected life of path j is R j , so each path should satisfy that

((LL K + 1 k=K C k )/XY ) × r b × N GOF F × S ≤ R j ( 9
)
If there is the

C k (1 ≤ k ≤ K -1)
which not transmitted by this path, it is transmitted by the other potential paths with lower priority level.

IV. ROBUST SUPER-RESOLUTION ALGORITHM

Although adaptive error-resilient video transmission can reduce the transmission distortion, it can not exterminate the packet loss which has a devastating effect on visual quality. In this section, we propose a robust SR algorithm taking into consideration the various packet loss

A. Simplified Estimator

Motivated by the model of [START_REF] Bajic | Adaptive MAP Error Concealment for Dispersively Packetized Wavelet-Coded Images[END_REF], here we propose a simplified estimator to estimate the lost coefficients. Since LL subband provide basic information (low frequency) for original image, missing samples in approximation subband LL are estimated prior to processing the high frequency subbands in LH, HL, and HH. Therefore, different strategies are employed to deal with the different kinds of packet loss.

In the case of the LL subband packet loss, as the correlation of the wavelet coefficients is much less than the high-frequency subbands, it is difficult to use a common interpolation method to estimate the lost coefficients precisely. As a result, we propose a low-complexity solution which can replace the commonly used single interpolation mask by a set of masks. In this case, each of them is adapted to a specific direction of the predominant spatial correlation. Here we define the correlation from the aspects of horizontal and vertical direction respectively and use general 5 × 5 interpolation mask presented in Fig. 3

(a). The parameters

A 0 ∼ A 3 , B 0 ∼ B 3 and C 0 ∼ C 3
are weights for the corresponding neighboring coefficients. The weights in each mask are chosen according to the predominant correlation direction (horizontal or vertical) and according to the degree of correlation (strong or weak). In order to measure the predominant correlation direction and the degree of correlation we propose the following algorithm:

After the wavelet decomposition, the sender bi-linearly interpolates each scaling coefficients as if it is lost. This process is done twice: a first approximation is obtained by using a horizontal interpolation; a second approximation by using a vertical interpolation. The horizontal interpolation pass only calculates the mean value of the left and right neighbors and the vertical interpolation pass simply calculates the mean value of the upper and lower neighbors. In this way, two approximations of the subband LL k are created: LL k h and LL k v . The sender then calculates the sum of the absolute differences (SAD) values for these two subbands compared to the original LL k subband: SAD v and SAD h ,

SAD = i∈W |I(i) -O(i)| ( 10
)
where I and O denote the interpolated and original coefficients respectively, and W is the comparison region, here is a 5 × 5 mask. We define a directional correlation measure as follows:

G h-v = SAD h -SAD v ( 11
)
The value of G h-v tells us how much one direction is better for interpolation than the other one. We define five classes: (a) strong horizontal correlation

(G h-v > A), (b) weak horizontal correlation (A ≥ G h-v > B), (c) isotropic (B ≥ G h-v ≥ -B

), (d) weak vertical correlation (-B > G h-v ≥ -A) and (e) strong vertical correlation (-A > G h-v ). The resulting values of

A and B are A = 15 and B = 5.

• Mask (a):

A 0 = A 2 = 30, A 1 = A 3 = 20; B 0 = B 1 = B 2 = B 3 = -8; C 0 = C 3 = -5, C 1 = C 2 = -4; • Mask (b): A 0 = A 2 = 35, A 1 = A 3 = 25; B 0 = B 1 = B 2 = B 3 = -7; C 0 = C 3 = -5, C 1 = C 2 = -4; • Mask (c): A 0 = A 1 = A 2 = A 3 = 35; B 0 = B 1 = B 2 = B 3 = -10; C 0 = C 1 = C 2 = C 3 = -4; • Mask (d): A 0 = A 2 = 25, A 1 = A 3 = 35; B 0 = B 1 = B 2 = B 3 = -7; C 0 = C 3 = -4, C 1 = C 2 = -5; • Mask (e): A 0 = A 2 = 20, A 1 = A 3 = 30; B 0 = B 1 = B 2 = B 3 = -8; C 0 = C 3 = -4, C 1 = C 2 = -5;
In the case of missing samples in LH, HL, and HH subbands, we label the weighting factors as shown in Fig. 3(b). That is, weights connecting horizontal neighbors are labeled H 0 and H 1 , those connecting vertical neighbors V 0 and V 1 , diagonal neighbors D 0 , D 1 , D 2 , and D 3 . Note that the direction of low-pass filtering is the direction in which high correlation of samples may be expected. To exploit the correlation between the wavelet coefficients in high-frequency subbands, a linear estimated model is adopted to estimate the missing samples. So the weighting factors can be set that

• Mask (LH): In LH, H 0 = H 1 = 6, V 0 = V 1 = D 0 = D 1 = D 2 = D 3 = 1;
• Mask (HL): In HL,

V 0 = V 1 = 6, H 0 = H 1 = D 0 = D 1 = D 2 = D 3 = 1;
• Mask (HH): In HH,

D 0 = D 1 = D 2 = D 3 = 4, H 0 = H 1 = V 0 = V 1 = 1;
The value of G h-v can be sent as three bits (which represent the five classes) in each packet.

This causes nearly no additional transmission overhead and no computational overhead for the receiver. All calculations are done by the sender and for the scaling coefficients only. According to a number of experiments, for a wavelet decomposition with depth is 3, the scaling coefficients only 1.6% of the total number of the coefficients. It should be emphasized that these factors are obtained empirically on the basis of considerable experimentation.

B. Projection onto Convex Sets

In this subsection, a projection procedure is utilized to extract information hidden in a group of video frames to update the wavelet coefficients. Since these coefficients correspond to the high frequency information in the spatial domain, the exacted fine features from other frames augment the individual LR frame to a HR frame. The constructed convex set should satisfy the following two points: 1) enhance the resolution of the received images, 2) reduce the artifacts generated during the projection process. We account for them in the following and present the relevant notation descriptions in Table I.

Let f (n, t) ∈ L 2 (R 2 ) denotes the original HR image1 , which can be expanded as a sum of approximation component in the LL band and three detail components in the LH, HL and HH

α j,k ψ j,k (n, t) LL + j,k∈Z β h j,k ϕ h j,k (n, t) LH + j,k∈Z β v j,k ϕ v j,k (n, t) HL + j,k∈Z β d j,k ϕ d j,k (n, t) HH ( 12
)
where ϕ h j,k (n, t), ϕ v j,k (n, t) and ϕ d j,k (n, t) are the translated wavelets at the next coarse scale level that capture detail information in the horizontal, vertical and diagonal directions respectively, and ψ j,k (n, t)is the translated coarse scaling function. The approximation and detail wavelet coefficients are given by

α j,k = f (n, t)ψ j,k (n, t)dndt ( 13
)
β h j,k = f (n, t)ϕ h j,k (n, t)dndt ( 14
)
β v j,k = f (n, t)ϕ v j,k (n, t)dndt ( 15
)
β d j,k = f (n, t)ϕ d j,k (n, t)dndt ( 16
)
Let f c (n, t) the current constructed LR frame and f r (n, t) be the reference LR image. The convex set can be defined from the above four aspects:

C inter = { f (n, t)|C α inter , C h inter , C v inter , C d inter } ( 17
)
where

C α inter = { f ψ j,k dndt = f c } (18) C h inter = { f ϕ h j,k dndt = β h j,k = f r ϕ h j,k dndt} ( 19
)
C v inter = { f ϕ v j,k dndt = β v j,k = f r ϕ v j,k dndt} ( 20
)
C d inter = { f ϕ d j,k dndt = β d j,k = f r ϕ d j,k dndt} (21)
f (n, t) denotes the estimated value of the f (n, t). So the projection of f (n, t) to C inter (denoted by P inter ) is defined as

f (n, t) ≡ P inter [ f (n, t)] ≡ j,k∈Z f c ψ j,k (n, t) + j,k∈Z β h j,k ϕ h j,k (n, t) + j,k∈Z β v j,k ϕ v j,k (n, t) + j,k∈Z β d j,k ϕ d j,k (n, t) (22)
Next, two steps of wavelet transform operation are implemented on the image f (n, t) which is produced after the inter-frame projection. Firstly, we don't employ the down-sampling, and get the three high frequency bands such as LH 1 , HL 1 and HH 1 . Secondly, we employ the down-sampling, and get the low frequency band LL and other three high frequency bands LH 2 , HL 2 and HH 2 . In addition, wavelet transform operation is implemented on the LL band and non-sampling, so we can get three bands of LH 3 , HL 3 and HH 3 . At last, the LS (Least Square) estimation of prediction is utilized to get the three bands of LH, HL and HH. The convex can be constructed as follow:

C intra = { f (n, t)|C LH intra , C HL intra , C HH intra } ( 23
)
where of the noise magnitude. After projecting by P intra , we get (here we only take the LH part for example, the other two bands are similar to this)

C LH intra = {[r LH = LH - j,k∈Z β h j,k ϕ h j,k ] ∈ [-δ, δ]} (24) C HL intra = {[r HL = HL - j,k∈Z β v j,k ϕ v j,k ] ∈ [-δ, δ]} (25) C HH intra = {[r HH = HH - j,k∈Z β d j,k ϕ d j,k ] ∈ [-δ, δ]} (26)
(LH) = P intra [ LH] = LH +                        LH - j,k∈Z β h j,k ϕ h j,k , r LH > δ LH + j,k∈Z β h j,k ϕ h j,k , r LH ≤ -δ 0, else (27)
From the (LH) , (HL) , (HH) and the known LL, the HR image can be get easily. The flow chart of the whole SR algorithm is illustrated in Fig. 4.

V. SIMULATION RESULTS AND DISCUSSIONS

In this section, we conduct simulation experiments to study the performance of the proposed robust resolution-enhancement scheme in a distributed video streaming framework. First of all, we describe the simulation environment. Secondly, we present the main simulation results where we show the objective and subjective results of the performance of the proposed system under different scenarios. Finally, we conclude this section by summarizing the conclusions to be drawn based on the selected simulation results described.

In order to provide a meaningful comparison between our proposed approach and other alternative approaches, we consider use of a recent unbalanced MDC with UEP mentioned in [START_REF] Kim | Distributed Video Streaming Using Multiple Description Coding and Unequal Error Protection[END_REF] as a comparison system. This paper presents a distributed video streaming framework using unbalanced MDC and UEP under the video streaming framework that two senders simultaneously stream complementary descriptions to a single receiver over different paths. To minimize the overall distortion and exploit the benefits of multi-path transport when the characteristics of each path are different, this paper also propose an unbalanced MDC method for wavelet-based coders combined with a TCP-friendly rate allocation algorithm. In addition, three-level wavelet decomposition is applied to a group of 16 frames and the 3-D wavelet coefficients are divided into two unequal-sized groups according to the priority level. Each substream is independently protected using the Forward Error Correction (FEC) based UEP algorithm proposed in [START_REF] Kim | Error-resilient image and video transmission over the internet using unequal error protection[END_REF].

Because this method can not enhance the resolution of image, we utilize the proposed SR method to give a fair comparison. For simplicity, we note this method as unbalanced method.

In addition, a fixed wavelet decomposition K = 2 (the remaining is the same as our proposed approach) is compared with the flexible MDC; and traditional bilinear method (the remaining is the same as our proposed approach) is employed to compare with our SR algorithm. Similarly, the above two methods are noted as fixed method and bilinear method, respectively.

A. Simulation Environment

For these experiments, the two standard video sequences, Foreman and Weather forecast, are encoded with shifted 3-D SPIHT algorithm. These video sequences are 352 × 288 pixels per frame; frame rate F = 30f rames/s; down-sampling parameter q = 2; the blur is Gaussian blur where the support of the blurring kernel is 29; frame number of one GOF N GOF = 16. At the receiver, the desired HR frame is reconstructed from several LR 176 × 144 degraded frames transmitted by MANETs. In order for objective comparison, PSNR at the receiver relative to the original HR video sequence is used and its definition is

P SN R(dB) = 10 log 10 ( 255 2 M SE ) (28)
where M SE is the mean-square error between the original the reconstructed luminance frame.

To the network part, 30 nodes that move randomly at maximum speed 2m/s are dispersed in the area 200 × 200 square meters, and the routing algorithm is based on MRDSR (Multiple Route Dynamic Source Routing) [START_REF] Nasipuri | Performance of multipath routing for on-demand protocols in mobile ad-hoc networks[END_REF]. In addition, the packet size S = 512bytes and initial energy of nodes is 1 Joule with uniform distribution. It should be noted that all the simulation results in this section have been obtained using 30 runs in order to obtain statistically meaningful average values.

B. Selected Simulation Results and Discussions

In Fig. 5, we illustrate a plot of PSNR versus the packet loss rate P L with burst length L B = 4 for the Foreman sequence at r b = 96Kbps, which is the range of low-bit services.

The proposed method can be seen to achieve a much higher performance in terms of end-to-end PSNR compared to the representative fixed method which apply fixed wavelet decomposition level regardless of the condition of the network and unbalanced method which compulsively divided stream into two unbalanced substreams. For the above two methods, there is a considerable performance disadvantage due to the improper use of the decomposition level and data distribution. Obviously, for little loss transmission (P L ≤ 5%) the fixed method achieves almost the same performance compared to the proposed scheme, and proposed method only gets marginal performance gain compared to unbalanced method when (8% ≤ P L ≤ 10%). However, as P L increases, the performance gap is increased dramatically since when the packet loss rate is high, more packets are unsuccessfully delivered obviously, non-adaptive scheme, including fixed and unbalanced method, can not adapt transmission strategy to this case while proposed method employ more decomposition to guarantee the most important data successfully transmitted. For example, when P L = 5%, the 2-level decomposition is adopted by the proposed method, so the gap between the proposed method with the fixed method is only about 0.1 dB, and when P L = 10%, the decomposition is adaptive to 3-level, the gap between the proposed method with the unbalanced method is about 0.3 dB, while the gap become 1.0dB when the P L = 15% and 4-level decomposition is employed.

It should also be noted from Fig. 5 that the performance achieved by the proposed method is also super to the traditional bilinear method to get higher resolution. Though proposed SR method can only achieve little gain compared to the traditional bilinear method in the case of lossless transmission (P L = 0), the performance gap also increases sharply as the P L increases.

In particular, as can be seen from Fig. 5, the performance gap between proposed SR methods with bilinear comparison method is more than 1.5dB when P L ≥ 10%. The reason is that, when P L ≤ 5%, few packets are lost and correlation of the adjacent packets is strong, bilinear as a simply interpolation method can also provide a relatively accurate estimation, while when P L > 5% (especially P L ≥ 10%), the packet correlation is so weak that bilinear can't performs well in this case. To our proposed SR method, adjacent and current frames information is utilized to enhance the resolution of the received image, therefore, it can achieve a more satisfying performance whether packet loss rate high or not.

In Fig. 6, we repeat the results for Foreman sequence with r b = 256Kbps and L B = 4.

It can be seen that the performance gap between the fixed or unbalanced method with the proposed method is much larger than Fig. 5, which is the case for low-bit rate services, while Fig. 6 is for high-rate services. This follows the fact that, when the available bit rate is high, the reconstructed video quality benefits considerably from the use of flexible MDC substreams and SR reconstruction technique which uses adaptive strategy to adapt current network condition and correlation information hidden in adjacent frames to enhance the received image resolution. Still, it can be seen that when P L = 10%, the proposed method can achieve a performance gain of approximately 0.4dB compared to the unbalanced method, and 1.7dB compared to the bilinear interpolation method, and when P L = 15%, the gap increases to 1.3dB and 2.2dB, respectively.

As discussed previously, the Foreman sequence is a high-motion sequence, while the Weather forecast sequence is a low-motion sequence. In order to provide a more comprehensive evaluation of the proposed adaptive scheme, we repeat the results for Weather forecast sequence in Fig. 7 and Fig. 8, for r b = 96Kbps and r b = 256Kbps, respectively, and similar behaviors as in Fig. 5 and Fig. 6 are observed. It should be note that the performance gap between the proposed adaptive scheme and the compared methods are less obvious than that in Fig. 5 and Fig. 6 for the highmotion Foreman sequence, because the correlation between the adjacent frames increases as the low-motion sequence implies. However, the proposed adaptive scheme also has the advantage of other alternative methods no matter what the P L is.

Some subjective results to demonstrate the relative performance achieved by the proposed method are illustrated in Fig. 9 corresponding to the objective results in Fig. 8 for P L = 15%.

Clearly, in Fig. 9, the subjective results are consistent with the objective results in Fig. 8. In particular, the proposed method can maintain more visual information comparing to the other alternative methods.

C. Observations

Based on the selected objective and subjective simulation results described above, there are several main observations:

• The adaptive error-resilient strategy has played an important role in the whole video transmission system. Comparing to the fixed method or the unbalanced method, the performance of the adaptive strategy is greater than those of them, especially when the packet loss rate is high.

• The proposed SR algorithm actually can enhance the resolution of the received image, and much detail information is maintained by taking advantage of the projection onto convex sets.

Comparing to the traditional bilinear method, the proposed SR algorithm at least has the 0.5dB PSNR gain, furthermore, the advantage gets more evident as the packet loss rate increases.

• The proposed method has great robust. No matter the video sequence is high-motion or low-motion, the packet loss rate is high or low, the proposed method can perform well all the time.

VI. CONCLUSIONS AND FUTURE WORK

In this paper, we propose a robust resolution-enhancement scheme for video stream transmission over mobile ad-hoc networks. As detailed in the paper, the scheme can adaptively respond to the dynamic network condition by adjusting the coding fashion at the encoder and error protection strategy during the transmission process. Furthermore, the SR algorithm used in the proposed scheme is so robust that it performs well in presence of different kinds of packet loss rates. Experiment results demonstrate that the proposed scheme outperforms the competing methods under the basis of the same simulation condition. We should note that our proposed method is hard to provide a real-time processing in wireless video system, therefore, our future work is to reduce its complexity to adapt to the real-time wireless video transmission.

Fig. 1 .

 1 Fig. 1. The total architecture of video transmission and processing

Fig. 2 .

 2 Fig. 2. Structure of the spatiotemporal relation of 3-D SPIHT

Fig. 3 .

 3 Fig. 3. Labeling of the weights used in calculation at the missing sample.

Fig. 4 .

 4 Fig. 4. Flow chart of the proposed robust SR method

Fig. 5 .

 5 Fig. 5. Performance achieved by proposed method for the Foreman sequence, at the r b = 96Kbps and L B = 4.

Fig. 6 .

 6 Fig. 6. Performance achieved by proposed method for the Foreman sequence, at the r b = 256Kbps and L B = 4.

Fig. 7 .

 7 Fig. 7. Performance achieved by proposed method for the Weather forecast sequence, at the r b = 96Kbps and L B = 4.

Fig. 8 .

 8 Fig. 8. Performance achieved by proposed method for the Weather forecast sequence, at the r b = 256Kbps and L B = 4.

Fig. 9 .

 9 Fig. 9. Subjective results achieved by proposed method and other comparison schemes, for the Weather forecast at r b = 256Kbps, L B = 4 and P L = 15%. (a) bilinear method; (b) fixed method; (c) unbalanced method; (d) proposed method.

the original value of f (n, t) can be achieved by expanding the LR image f (n, t) using bi-linear method

ACKNOWLEDGMENTS

This work is supported by the International Project PRA-SI (financed by France and China government) under Grant No. SI04-03, the Key Project of Nature Science Foundation of Jiangsu (China) under Grant BK2007729 and the Climbing Plan of Nanjing University of Posts and Telecommunications under Grant NY207061. Moreover, we also thank the anonymous reviewers for insightful comments and suggestions.


Pratik Gajane
email: pratik.gajane@orange.com

Tanguy Urvoy
email: tanguy.urvoy@orange.com

Fabrice Clérot
email: fabrice.clerot@orange.

A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits (extended version)

We study the K-armed dueling bandit problem which is a variation of the classical Multi-Armed Bandit (MAB) problem in which the learner receives only relative feedback about the selected pairs of arms. We propose an efficient algorithm called Relative Exponential-weight algorithm for Exploration and Exploitation (REX3) to handle the adversarial utility-based formulation of this problem. We prove a finite time expected regret upper bound of order O( K ln(K)T ) for this algorithm and a general lower bound of order Ω( √ KT ). At the end, we provide experimental results using real data from information retrieval applications.

Introduction

The K-armed dueling bandit problem is a variation of the classical Multi-Armed Bandit (MAB) problem introduced by [START_REF] Yue | Interactively optimizing information retrieval systems as a dueling bandits problem[END_REF] to formalize the exploration/exploitation dilemma in learning from preference feedback. In its utility-based formulation, at each time period, the environment sets a bounded value for each of K arms. Simultaneously the learner selects two arms and wagers that one of the arms will be better than the other. The learner only sees the outcome of the duel between the selected arms (i.e. the feedback indicates which of the selected arms has better value) and receives the average of the rewards of the selected arms. The goal of the learner is to maximize her cumulative reward. The difficulty of this problem stems from the fact that the learning algorithm has no way of directly observing the reward of its actions. This is a perfect example of partial monitoring problem as defined in [START_REF] Piccolboni | Discrete prediction games with arbitrary feedback and loss[END_REF].

Proceedings of the 32 nd International Conference on Machine Learning, Lille, France, 2015. JMLR: W&CP volume 37. Copyright 2015 by the author(s).

Relative feedback is naturally suited to many practical applications like user-perceived product preferences, where a relative perception: "A is better than B" is easier to obtain than its absolute counterpart: "A value is 42, B is worth 33". Another important application of dueling bandits comes from information retrieval systems where users provide implicit feedback about the provided results. This implicit feedback is collected in various ways e.g. a click on a link, a tap, or any monitored action of the user. In all these ways however, this kind of feedback is often strongly biased by the model itself (the user cannot click on a link which was not proposed).

To remove this bias in search engines, [START_REF] Radlinski | Active exploration for learning rankings from clickthrough data[END_REF] propose to interleave the outputs of different ranking models: the model which scores a click wins the duel. The accuracy of this interleave filtering method was highlighted in several experimental studies [START_REF] Radlinski | Active exploration for learning rankings from clickthrough data[END_REF][START_REF] Joachims | Evaluating the accuracy of implicit feedback from clicks and query reformulations in web search[END_REF][START_REF] Chapelle | Large-scale validation and analysis of interleaved search evaluation[END_REF].

Main contribution

The main contribution of this article is an algorithm designed for the adversarial utility-based dueling bandit problem in contrast to most of the existing algorithms which assume a stochastic environment.

Our algorithm, called Relative Exponential-weight algorithm for Exploration and Exploitation (REX3), is a non-trivial extension of the Exponential-weight algorithm for Exploration and Exploitation (EXP3) algorithm (Auer et al., 2002b) to the dueling bandit problem. We prove a finite time expected regret upper bound of order O( K ln(K)T ) and develop an argument initially proposed by [START_REF] Ailon | Reducing dueling bandits to cardinal bandits[END_REF] to exhibit a general lower bound of order Ω( √ KT ) for this problem.

These two bounds correspond to the original bounds of the classical EXP3 algorithm and the upper bound strictly improves from the Õ(K √ T ) obtained by existing generic partial monitoring algorithms. 1 Our experiments on information retrieval datasets show that the anytime version of REX3 is a highly competitive algorithm for dueling bandits, especially in the initial phases of the runs where it clearly outperforms the state of the art.

Outline

This article is organized as follows: In section 2, we give a brief survey on dueling bandits with section 2.3 dedicated to the adversarial case. Most notations and formalizations are introduced in this section. Secondly, in section 3, we formally describe REX3 with its pseudo-code. Then, in section 4.1, we provide the upper bound on the expected regret of REX3. Furthermore, in section 4.2, we provide the lower bound on the regret of any algorithm attempting to solve the adversarial utility-based dueling bandit problem. Section 5 begins with an empirical study of the bound given in section 4.1. It then provides comparisons of REX3 with state-of-the art algorithms on information retrieval datasets.

The conclusion is provided in section 6.

Previous Work and Notations

The conventional MAB problem has been well studied in the stochastic setting as well as the (oblivious) adversarial setting (see [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF]. These MAB algorithms are designed to optimize exploration and exploitation in order to control the cumulative regret which is the difference between the gain of a reference strategy and the actual gain of the algorithm.

Exponential-weight algorithm for Exploration and Exploitation

Of particular interest are the Exponential-weight algorithm for Exploration and Exploitation (EXP3) and its variants presented by Auer et al. (2002b) for the adversarial bandit setting. For a fixed horizon T and K arms, the EXP3 algorithm provides an expected cumulative regret bound of order O( K ln(K)T ) against the best single-arm strategy. This algorithm is indeed adversarial because it does not require a stochastic assumption on the rewards. It is although not anytime because it requires the knowledge of the horizon T to run properly. A "doubling trick" solution is proposed by Auer et al. (2002b) to preserve the regret bound when T is unknown. It consists of running EXP3 in a carefully designed sequence of increasing epochs. Another elegant solution was later proposed by [START_REF] Seldin | Evaluation and analysis of the performance of the exp3 Algorithm in stochastic environments[END_REF] for the same purpose.

1 The notation Õ(•) hides logarithmic factors.

Previous work on stochastic dueling bandits

The dueling bandits problem is recent, although related to previous works on computing with noisy comparison (see for instance [START_REF] Karp | Noisy binary search and its applications[END_REF]. This problem also falls under the framework of preference learning [START_REF] Freund | An efficient boosting algorithm for combining preferences[END_REF][START_REF] Liu | Learning to rank for information retrieval[END_REF]Fürnkranz and Hüllermeier, 2010) which deals with learning of (predictive) preference models from observed (or extracted) preference information i.e. relative feedback which specifies which of the chosen alternatives is preferred. Most of the articles hitherto published on dueling bandits consider the problem under a stochastic assumption. [START_REF] Yue | Interactively optimizing information retrieval systems as a dueling bandits problem[END_REF] propose an algorithm called Dueling Bandit Gradient Descent (DBGD) to solve a version of the dueling bandits problem where context information is provided. They approach (contextual) dueling bandits as an on-line convex optimization problem. [START_REF] Yue | The k-armed dueling bandits problem[END_REF] propose an algorithm called Interleaved Flitering (IF). Their formulation is stochastic and matrixbased: for each pair (i, j) of arms, there is an unknown probability P i,j for i to win against j. This preference matrix P of size K × K must satisfy the following symetry property:

∀i, j ∈ {1, . . . , K}, P i,j + P j,i = 1

(1)

Hence on the diagonal: P i,i = 1 2 ∀i ∈ {1, . . . , K}. Let i * be the "best arm" (as we will see later, this best arm coincides with the notion of Condorcet winner). [START_REF] Yue | The k-armed dueling bandits problem[END_REF] define the regret incurred at the time instant t when arms a and b are pulled as:

r a,b = P i * ,a + P i * ,b -1 2 ∈ (0, 1 2 ) (2)
We will call this regret a Condorcet regret.

For the IF algorithm to work, the P matrix is expected to satisfy several strong assumptions: strict linear ordering, stochastic transitivity, and stochastic triangular inequality. Under these three assumptions IF is guaranteed to suffer an expected cumulative regret of order O(K log T ).

Yue and Joachims (2011) introduce Beat The Mean (BTM), an algorithm which proceeds by successive elimination of arms. This algorithm is less constrained than IF as it also applies to a relaxed setting where the preference matrix can slighlty violate the stochastic transitivity assumption. Its cumulative regret bound is of order O(γ 7 K log T ) where γ is here a known parameter. [START_REF] Urvoy | Generic exploration and K-armed voting bandits[END_REF] propose a generic algorithm called SAV-AGE (for Sensitivity Analysis of VAriables for Generic Exploration) which does away with several assumptions made in the previous algorithms e.g. existence of inherent values of arms, existence of a linear order amongst arms. In this general setting, the SAVAGE algorithm obtains a regret bound of order O(K2 log T ). The key notions they introduce for dueling bandits are the Copeland, Borda and Condorcet scores [START_REF] Charon | An updated survey on the linear ordering problem for weighted or unweighted tournaments[END_REF]. The Borda score of an arm i on a preference matrix P is K j=1 P i,j and its Copeland score is K j=1 P i,j > 1 2 (We use . . . to denote the indicator function). If an arm has a Copeland score of K -1, which means that it defeats all the other arms in the long run, it is called a Condorcet winner. The existence of a Condorcet winner is the minimum assumption required for the Condorcet regret as defined on equation (2) to be applicable. There exists however some datasets like MSLR30K (2012) where this Condorcet condition is not satisfied. Zoghi et al. (2014a) extend the Upper Confidence Bound (UCB) algorithm (Auer et al., 2002a) and propose an algorithm called Relative Upper Confidence Bound (RUCB) provided that the preference matrix admits a Condorcet winner. They retrieve an O(K log T ) bound under this sole assumption. Unlike the previous algorithms, RUCB is an anytime dueling bandits algorithm since it does not require the time horizon T as input. [START_REF] Ailon | Reducing dueling bandits to cardinal bandits[END_REF] propose three methods (DOUBLER, MULTISMB, and SPARRING) to reduce the stochastic utility-based dueling bandits problem to the conventional MAB problem. A stochastic dueling bandits problem is utility-based if the preference is the result of comparisons of the individual utility/reward of the arms. This is a strong restriction from the general -matrix-based -formulation of the problem.

More formally, there are K probability distributions v 1 , . . . , v K over [0, 1] associated respectively with arms 1, . . . , K. Let µ 1 , . . . , µ K be the respective means of v 1 , . . . , v K . When an arm a is pulled, its reward/utility x a is drawn from the corresponding distribution v a 2 . Let i * ∈ arg max µ i be an optimal arm. The regret incurred at the time instant t when arms a and b are pulled is defined as:

r a,b (t) = 2x i * -x a -x b 2 (3)
We will call this regret a bandit regret. With randomized tie-breaking we can rebuild the preference matrix:

P i,j = P(x i > x j ) + 1 2 P(x i = x j )
When all v i are Bernoulli laws, this reduces to:

P i,j = µ i -µ j + 1 2 (4)
Note that if µ i > µ j for some arms i and j, then P i,j > 1 2 . The best arm in the usual bandit sense hence coincides with the Condorcet winner (which turns out to be the Borda winner too) on the matrix formulation and the expected bandit regret is twice the Condorcet regret as defined in (2):

Er a,b = 2µ i * -µ a -µ b 2 = P i * ,a + P i * ,b -1 = 2r a,b
Several other models and algorithms have been proposed since to handle stochastic dueling bandits. We can cite [START_REF] Busa-Fekete | Top-k selection based on adaptive sampling of noisy preferences[END_REF]2014;[START_REF] Zoghi | Relative confidence sampling for efficient online ranker evaluation[END_REF][START_REF] Zoghi | MergeRUCB: A method for large-scale online ranker evaluation[END_REF]. See also (Busa-Fekete and Hüllermeier, 2014) for an extensive survey of this domain.

Adversarial dueling bandits

The bibliography on stochastic dueling bandits is flourishing, but the results about adversarial dueling bandits remain quite scarce.

A utility-based formulation of the problem is however proposed in Ailon et al. (2014, section 6). In this setting, as in classical adversarial MAB, the environment chooses beforehand an horizon T and a sequence of utility/reward vectors

x(t) = (x 1 (t), . . . , x K (t)) ∈ [0, 1] K for t = 1, . . . , T .
The learning algorithm aims at controling the bandit regret against the best single-arm strategy, as defined in (3), by choosing properly the pairs of arms (i, j) to be compared.

To tackle this problem, [START_REF] Ailon | Reducing dueling bandits to cardinal bandits[END_REF] suggest to apply the SPARRING reduction algorithm, although originally designed for stochastic settings, with an adversarial bandit algorithm like EXP3 as a black-box MAB. According to the authors, the SPARRING reduction preserves the O( √ KT ln K) upper bound of EXP3. This algorithm uses two separate MABs (one for each arm). As a consequence, when it gets a relative feedback about a duel (i, j), the left instantiation of EXP3 only updates its weight for arm i while the right instantiation only updates for j. The algorithm we propose improves from this solution by centralizing information for both arms on a single weight vector.

As mentionned earlier, the dueling bandits problem is a special instance of a partial monitoring game [START_REF] Piccolboni | Discrete prediction games with arbitrary feedback and loss[END_REF][START_REF] Cesa-Bianchi | Combinatorial bandits[END_REF][START_REF] Bartók | Partial monitoring -classification, regret bounds, and algorithms[END_REF]. A partial monitoring game is defined by two matrices: a loss matrix L and a feedback matrix H. These two matrices are known by the learner. At each round, the learner chooses an action a while the environment simultaneously chooses an outcome (say x). The learner receives a feedback H(a, x) and suffers (in a blind manner) a loss L(a, x).

It is straightforward to encode the classical MAB as a finite partial monitoring game: the actions are arms indices a ∈ {1, . . . , K} while the environment outcomes are reward vectors x(t) = (x 1 (t), . . . , x K (t)) ∈ [0, 1] K . The loss and feedback matrices are respectivly defined by L(a, x) = -x a and H(a, x) = x a . For the utility-based dueling bandits problem, the learner's actions are the duels (a, b) ∈ {1, . . . , K} 2 and the environment outcomes are reward vectors. If we constrain the rewards to be binary it turns out to be a finite partial monitoring game. The Loss matrix is defined by

L ((a, b), x) = -(x a + x b )/2 and the feedback by H ((a, b), x) = ψ(x a -x b ) where ψ is a non- decreasing transfer function such that ψ(0) = 0 (usually ψ(x) = x > 0 or ψ(x) = x).
There are only four classes of finite partial monitoring games in term of time lower bounds, namely: trivial games with no regret at all, "easy" games with Θ √ T minimax regret, "hard" games with Θ T 2/3 , and hopeless' games with Ω (T ) regret.

Several generic partial monitoring algorithms were recently proposed for both stochastic and adversarial settings (see Bartók et al., 2014, for details). If we except GLOBAL-EXP3 [START_REF] Bartók | A near-optimal algorithm for finite partial-monitoring games against adversarial opponents[END_REF] which tries to capture more finely the structure of the games, these algorithms only focus on the time bound and perform inefficiently when the number of actions grows.

In a dueling bandit the number of non-duplicate actions is actually K(K + 1)/2 and these algorithms, including GLOBALEXP3, provide at best a Õ K √ T regret guarantee. The dedicated algorithm that we propose is using the preference feedback more efficiently.

Relative Exponential-weight Algorithm for Exploration and Exploitation

The pseudo-code for the algorithm we propose is given in Algorithm 1. As previously stated on Section 2.3, this algorithm is designed to apply for the adversarial utility-based dueling bandits problem.

It is similar to the original EXP3 from step 1 to step 6 where it computes a distribution

p(t) = (p 1 (t), . . . , p K (t))
which is a mixture of a normalized weighing of the arms w i / i w i and a uniform distribution 1/K. As in EXP3, this uniform probability is introduced to ensure a minimum exploration of all arms.

At step 7, the algorithm draws two arms a and b independently according to p(t). At step 8, the algorithm gets ψ(x ax b ) as relative feedback . Note that, since arms are drawn with replacement, we may have a = b, in which case the algorithm will get no information. This event is indeed expected to become frequent when the p(t) distribution becomes peaked around the best arms. This necessity for a regret-minimizing dueling bandits algorithm to renounce getting information when confident about its decision is a structural bias toward exploitation that is not encountered in classical bandits.

Step 8 is the big difference from EXP3; because we only have access to the relative ψ(x ax b ) value, we have no mean to estimate the individual rewards x a or x b . There is however a solution to circumvent this problem: the best arm in expectation at time t is not only the one which maximizes the absolute reward. It is indeed the one which maximizes the regret of any fixed strategy π(t) against it:

arg max i x i (t) = arg max i x i (t) -E a∼π(t) x a .
This reference strategy could be a single-arm or uniform strategy but playing a suboptimal strategy to get a reference has a cost in terms of regret. One of our contributions is to show that the algorithm may use its own strategy as a reference.

At step 9, the condition a = b is only a slight improvement for matrix-based dueling bandits where the outcome of a duel of an arm against itself is randomized as in (4).

At steps 10 and 11, the weights of the played arms are updated. This update process is the core of our algorithm, it will be detailed in Section 4.

Step 13 is only required for the anytime version of the algorithm. It will be explained in section 5.2.

Algorithm 1 REX3: Exp3 with relative feedback 1: Parameters: γ ∈ (0, 1] 2: Initialization: w i (1) = 1 for i = 1, . . . , K.

3: for t = 1, 2, . . . do 4:

for i = 1, . . . , K do 5: Set p i (t) ← (1 -γ) wi(t) K j=1 wj (t) + γ K 6:
end for 7:

Pull two arms a and b chosen independently according to the distribution (p 1 (t), . . . , p K (t)).

8:

Receive relative feedback ψ(

x a -x b ) ∈ [-1, +1] 9: if a = b then 10: Set w a (t + 1) ← w a (t) • e γ K ψ(xa -x b ) 2pa 11: Set w b (t + 1) ← w b (t) • e -γ K ψ(xa -x b ) 2p b 12:
end if

13:

Update γ (for anytime version) 14: end for

Analysis

For the analysis, we focus on the simple case where ψ is the identity. It provides a ternary win/tie/loss feedback if we assume binary rewards. The main difference between EXP3 and our algorithm is at steps 10 and 11 of Algorithm 1, where we update the weights according to the duel outcome: the winning arm is gratified while the loser is penalized. This 'punitive' approach of exponential weighing departs from EXP3 and other weighing algorithms which gratify the most rewarding arms while kindly ignoring the nonrewarding ones [START_REF] Freund | Adaptive game playing using multiplicative weights[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF].

Upper bound for REX3

In this section, we provide a finite-horizon non-stochastic upper bound on the expected regret against the best single action policy.

The steps 10-11 on Algorithm 1 are equivalent to operating for each arm i an update of the form:

w i (t + 1) = w i (t) • e γ K ĉi(t)
where

ĉi (t) = i = a ψ(x a -x b ) 2p a + i = b ψ(x b -x a ) 2p b (5)
One big difference with EXP3 is that ĉi (t) not an estimator of the reward x i (t). We instead have:

Lemma 1. E [ĉ i (t)|(a 1 , b 1 ), .., (a t-1 , b t-1 )] = E a∼p(t) ψ(x i (t)-x a (t))
The proof of the lemma is given in Appendix B.2.

If ψ is the identity then Eĉ i (t) = x i (t) -E a∼p(t) x a (t) in which case we estimate the expected instantaneous regret of the algorithm against arm i. If we rather take ψ(x) = x > 0 , then Eĉ i (t) = P a∼p(t) (x i (t) > x a (t)), i.e. the probability for the algorithm to select an arm defeated by i.

Let G max = max i T t=1 x i (t) be the best single-arm gain, and let

G alg = 1 2 T t=1 x a (t) + x b (t) be the gain of the al- gorithm. Let EG unif = 1 K T t=1 K i=1
x i (t) be the average value of the game (i.e. the expected gain of the uniform sampling strategy).

Theorem 1. If the transfer function ψ is the identity and γ ∈ (0, 1 2 ), then,

G max -E(G alg ) ≤ K γ ln(K) + γτ where τ = e • EG alg -(4-e) • EG unif .
The proof of this theorem is detailed on Appendix B.

Provided that EG alg ≤ G max and EG unif ≥ G min , where G min = min i T t=1 x i (t) is the gain of the worst single-arm strategy, we can simplify the bound into:

Corollary 1. G max -EG alg ≤ Kln K γ + γ (eG max -(4-e) G min )
As in (Auer et al., 2002b, section 3), since K γ ln(K) + γτ is convex, we can obtain the optimal γ on (0, 1 2 ):

γ * = min 1 2 , K ln(K) τ (6)
Substituting γ in Corollary 1 with its optimal value from eq. ( 6) we obtain:

G max -E(G alg ) ≤ 2 K ln(K) [eG max -(4-e) G min ]
Hence:

Corollary 2. When γ = min 1 2 , K ln(K) τ , the ex- pected regret of REX3 (Algorithm 1) is O K ln(K)T .
The upper bound of REX3 for adversarial utility-based dueling bandits is hence the same as the one of EXP3 for aversarial MABs. For a high-number of arms or a short term horizon, this bound is competitive against the O (K ln(T ))

or O K 2 ln(T ) existing bounds for stochastic dueling bandits.

Lower bound for dueling bandits algorithms

To provide a lower bound on the regret of any dueling bandits algorithm, we use a reduction to the classical MAB problem suggested by [START_REF] Ailon | Reducing dueling bandits to cardinal bandits[END_REF].

Algorithm 2 Reduction to classical MAB 1: DBA.init() 2: Set t = 1 3: repeat 4:

(a t , b t+1 ) ← DBA.decide() 5:

x at ← CBE.get reward() 6:

x bt+1 ← CBE.get reward()

7:
DBA.update((a t , b t+1 ), (x atx bt+1 ))

8:

t = t + 2 9: until t ≥ T
Algorithm 2 gives an explicit formulation of this reduction by using a generic dueling bandits algorithm (DBA) as a black-box having the following public sub-routines: init(), decide() and update(). The classical bandit environment (CBE) provides get reward() which returns the reward of the input arm. The expected classicalbandit gain of Algorithm 2 will be twice the expected gain of the black-box dueling bandits it uses.

It is important to note that this reduction only works for stochastic settings where the expected reward of each arm remains the same across time instants. According to Theorem 5.1 given by Auer et al. (2002b, section 5), for K ≥ 2, the expected regret in the classical bandit setting is Ω( √ KT ) (assuming T is large enough i.e. T ≥ √ KT ). Since this result is obtained with a stationary stochastic distribution, by extension, the expected regret in the dueling bandits setting cannot be less than Ω( √ KT ).

Theorem 2. For any number of actions K ≥ 2 and large enough time horizon T (i.e. T ≥ √ KT ), there exists a distribution over assignments of rewards such that the expected cumulative regret of any utility-based dueling bandits algorithm cannot be less than Ω( √ KT ).

Experiments

To evaluate REX3 and other dueling bandits algorithms, we have applied them to the online comparison of rankers for search engines by interleaved filtering [START_REF] Radlinski | Active exploration for learning rankings from clickthrough data[END_REF]. A search-engine ranker is a function that orders a collection of documents according to their relevancy to a given user search query. By interleaving the output of two rankers and tracking on which ranker's output the user did click, we are able to get an unbiased feedback about the relative quality of these two rankers. Given K rankers, the problem of finding the best ranker is indeed a K-armed dueling bandits.

In order to obtain reproducible and comparable results, we adopted the stochastic matrix-based experiment setup already employed by [START_REF] Yue | Beat the mean bandit[END_REF]; Zoghi et al. (2014a;b;[START_REF] Zoghi | MergeRUCB: A method for large-scale online ranker evaluation[END_REF] with both the cumulative Condorcet regret as defined by [START_REF] Yue | The k-armed dueling bandits problem[END_REF] and the accuracy i.e. the best arm hit-rate over the runs:

1 N n (a, b) = (i * , i *
) . This experimental setup uses real search engines' logs to build empirical preference matrices. The duel outcomes are then simulated on these matrices. We used several preference matrices issued from namely: ARXIV dataset [START_REF] Yue | Beat the mean bandit[END_REF], LETOR NP2004 dataset [START_REF] Liu | LETOR: Benchmark dataset for research on learning to rank for information retrieval[END_REF], and MSLR30K dataset. The last dataset distinguishes three kinds of queries: informational, navigational and perfecthit navigational (MSLR30K, 2012). These matrices are courtesy of Zoghi et al. (2014b)'s authors.

Empirical validation of Corollary 1

We have used LETOR NP2004 and MSLR30K datasets (resricted to 64 rankers) to compare the average Condorcet regret of 100 runs of REX3 with T = 10 5 to the corresponding halved 3 theoretical bounds from Corollary 1 for various values of γ. The results of this experiment are suma-3 As mentioned at the end of section 2.2, the utility-based bandit regret is indeed twice the Condorcet regret as defined in (2). rized in Figure 1. We plotted two theoretical curves: one with a conservative G max = T /2, and a riskier one with G max = T /4. This experiment illustrates the dual impact of the γ parameter on the exploration/exploitation tradeoff: a low value reduces both the exploration and the reactivity of the algorithm to unexpected feedbacks and a high value tends to uniformize exploration while increasing reactivity. It also shows that the theoretical optimal γ * we obtain with Equation ( 6) is a good guess even with a conservative upper-bound for G max .

Interleave filtering simulations

For our experiments we have considered the following state of the art algorithms: BTM [START_REF] Yue | Beat the mean bandit[END_REF] with γ = 1.1 and δ = 1/T (explore-then-exploit setting), Condorcet-SAVAGE [START_REF] Urvoy | Generic exploration and K-armed voting bandits[END_REF] with δ = 1/T , RUCB (Zoghi et al., 2014a) with α = 0.51, and SPAR-RING coupled with EXP3 [START_REF] Ailon | Reducing dueling bandits to cardinal bandits[END_REF]. We also took the uniform sampling strategy RANDOM as a baseline. We considered three versions of REX3: two non-anytime versions where the optimal γ * is computed beforehand according to (6) with G max set respectively to T /2 and T /10 and one anytime version where γ * is recomputed at each time step according to (6) (see [START_REF] Seldin | Evaluation and analysis of the performance of the exp3 Algorithm in stochastic environments[END_REF], for details about this form of "doubling trick").

A point which makes the comparison difficult is that some algorithms are anytime while others require the horizon as input. For anytime algorithms, namely RANDOM, RUCB and REX3 with adaptive γ, we displayed the average over 100 runs of the progressive accumulation of regret while for non-anytime algorithms, namely BTM, CSAVAGE, SPAR-RING and other versions of REX3, we displayed the average over 50 runs of the final cumulative regret for several fixed and known horizons. This protocol is slightly favorable to non-anytime algorithms which benefit from more information. However, for elimination algorithms like BTM and CSAVAGE the difference between the anytime regret and the non-anytime regret is small. For adversarial algorithms like SPARRING and REX3 the "doubling trick" can be applied to make them anytime: the adaptive γ version of REX3 is an example of such a fixed-to-anytime transformation.

The results of these experiments are summarized in Figure 2, and 3. Furthermore, similar experiments are given as extended material.

As expected, the adversarial-setting algorithms SPAR-RING and REX3 follow an O( √ T ) regret curve while the stochastic-setting algorithms follow an O(ln T ) curve. Among the adversarial-setting algorithms, REX3 is shown to outperform SPARRING on all datasets. In the long run, adversarial-setting algorithms continue exploring and cannot compete in terms of regret against stochastic-setting algorithms, but the accuracy curves show that the cost of this exploration is very small. Moreover, for small horizons or high number of rankers, REX3 is extremely competitive against other algorithms. This difference is clearly illustrated on the left-hand side of Figure 3 where we show the evolution of the expected cumulative regret at a fixed time horizon (T = 10 5 ) according to the number of arms. To obtain this plot we averaged the regret over 50 runs. For each K and each run we sampled uniformly K dimensions of the original 136×136 MSLR30K navigational preference matrix.

Conclusion

We proposed REX3, an exponential weighing algorithm for adversarial utility-based dueling bandits. We provided both an upper and a lower bound for its expected cumulative regret. These two bounds match the original bounds of the classical EXP3 algorithm. A thorough empirical study on several information retrieval datasets has confirmed the validity of these theoretical results. It also showed that REX3 and especially its anytime version with adaptive γ are competitive solutions for dueling bandits, even when compared to stochastic-setting algorithms in a stochastic environment.

A. Proof Sketch for Theorem 1

The general structure of the proof is similar to the one of (Auer et al., 2002b, section 3), but, as explained before, the ĉi (t) estimator we use differs from the one of EXP3 because it gives an instantaneous regret estimate instead of an absolute reward estimate. As such, it may reach negative values and the w i (t) weights may decrease with time. We only give here a sketch of proof, stressing on the differences from (Auer et al., 2002b). An unfamiliar reader may refer to the extended version for step-by-step details.

Proof. Let W t = w 1 (t)+w 2 (t)+• • •+w K (t).
As in EXP3 proof we consider:

W t+1 W t = K i=1 p i (t) -γ/K 1 -γ e (γ/K)ĉi(t)
The inequality e x ≤ 1 + x + (e -2)x 2 is tight for x ∈ [0, 1] but it remains valid for negative values, hence:

W t+1 W t ≤ 1 - γ 2 /K 1 -γ       1 K K i=1 ĉi (t) =-M1       + (e -2)γ 2 /K 1 -γ       1 K K i=1 p i (t)ĉ i (t) 2 =M2      
As in EXP3 we take the logarithm and sum over t. We get for any j:

T t=1 γ K ĉj (t) -ln(K) ≤ γ 2 /K 1 -γ M 1 + (e -2)γ 2 /K 1 -γ M 2
By taking the expectation over the algorithm's randomization, we obtain for any j:

T t=1 γ K E ∼p ĉj (t) (8) -ln(K) ≤ γ 2 /K 1 -γ T i=t E ∼p M 1 (9) + (e -2)γ 2 /K 1 -γ T i=t E ∼p M 2 (10) (7)
From Lemma 1 we directly get the expected regret against j on the left side of the inequality:

E ∼p ĉj (t) = x j -E ∼p (x a ) (8)
By averaging (8) over the arms, we obtain: The following result is detailled in the extended version:

E ∼p(t) M 1 = - 1 K K i=1 E ∼p ĉi (t) = E(x a ) - 1 K K i=1 x i (9)
E ∼p(t) M 2 ≤ 1 2 E(x a ) + 1 2K K i=1 x i (10)
From Lemma 1, ( 9), ( 10), and by definition of G max , EG alg , and EG unif , the inequality (7) rewrites into:

G max -EG alg - K ln K γ ≤ γ 1 -γ (EG alg -EG unif ) + (e-2)γ 2(1 -γ) (EG alg + EG unif )
Assuming γ ≤ 1 2 we finally obtain:

G max -EG alg ≤ K ln K γ + γ (eEG alg -(4-e) EG unif )
An Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits (supplementary material)

B. Detailed Proof of Theorem 1

For better readabilty, we simply write a, b instead of a t , b t when referring of the arms chosen by the algorithm. We also frequently drop the time indices for p . (t) and x . (t). See Table 1 for an exhaustive list of notations.

Proof.

Let W t = w 1 (t) + w 2 (t) + • • • + w K (t) W t+1 W t = K i=1 w i (t + 1) W t = K i=1 w i (t) W t e (γ/K)ĉi(t)
By substituting the values of wi(t) Wt , we get:

W t+1 W t = K i=1 p i (t) -γ/K 1 -γ e (γ/K)ĉi(t)
Using the inequality e x ≤ 1 + x + (e -2)x 2 for x ≤ 1, we get:

W t+1 W t ≤ K i=1 p i (t) -γ/K 1 -γ (1 + (γ/K)ĉ i (t)) + K i=1 p i (t) -γ/K 1 -γ (e -2)(γ 2 /K 2 )ĉ i (t) 2 ≤ K i=1 p i (t) -γ/K 1 -γ =1 + γ/K 1 -γ       K i=1 p i (t)ĉ i (t) =0 see (12) - γ K K i=1 ĉi (t)       + (e -2)(γ 2 /K 2 ) 1 -γ K i=1 p i (t)ĉ i (t) 2 ≤ 1 + γ/K 1 -γ 0 - γ K K i=1 ĉi (t) + (e -2)(γ 2 /K 2 ) 1 -γ K i=1 p i (t)ĉ i (t) 2 ≤ 1 - γ 2 /K 1 -γ       1 K K i=1 ĉi (t) =-M1       + (e -2)(γ 2 /K) 1 -γ 1 K K i=1 p i (t)ĉ i (t) 2 =M2 (11) K i=1 p i (t)ĉ i (t) = K i=1 p i (t) i = a x a -x b 2p a + K i=1 p i (t) i = b x b -x a 2p b = x a -x b 2 + x b -x a 2 = 0 (12)
From ( 11) and ( 12), we obtain:

W t+1 W t ≤ 1 + γ 2 /K 1 -γ M 1 + (e -2)(γ 2 /K) 1 -γ M 2
Taking logarithms and using the inequality

1 + x ≤ e x ln W t+1 W t ≤ γ 2 /K 1 -γ M 1 + (e -2)(γ 2 /K) 1 -γ M 2
Summing over t, we get:

ln W T +1 W 1 ≤ γ 2 /K 1 -γ M 1 + (e -2)(γ 2 /K) 1 -γ M 2 (13)
For any arm j we have:

T t=1 γ K ĉj (t) -ln(K) ≤ ln W T +1 W 1 (14)
The proof of the above inequality is given in appendix B.1. By combining ( 13) and ( 14) , we get:

T t=1 γ K ĉj (t) -ln(K) ≤ γ 2 /K 1 -γ M 1 + (e -2)γ 2 /K 1 -γ M 2 (15)
Taking the expectation over the algorithm's randomization, we obtain:

T t=1 γ K E ∼p ĉj (t) Lemma 1 -ln(K) ≤ γ 2 /K 1 -γ T i=t E ∼p M 1 see (17) + (e -2)(γ 2 /K) 1 -γ T i=t E ∼p M 2 see (18)
From Lemma 1 which proof is detailed in appendix B.2, we have:

E ∼p ĉj (t) = x j -E ∼p (x a ) (16)
By averaging ( 16) over the arms, we obtain:

E ∼p(t) M 1 = E ∼p - 1 K K i=1 ĉi (t) = - 1 K K i=1 E ∼p ĉi (t) = E(x a ) - 1 K K i=1 x i (17)
The following result is detailled in appendix B.3:

E ∼p(t) M 2 = E ∼p(t) (p a + p b )(x a -x b ) 2 4Kp a p b = 1 2 E(x 2 a ) -E(x a ) 1 K K i=1 x i + 1 2K K i=1 x 2 i ≤ 1 2 E(x a ) -E(x a ) 1 K K i=1 x i + 1 2K K i=1 x i as ∀i, x i ∈ [0, 1] (18)
From Lemma 1, (17), and (18), we get for any j:

γ K T t=1 x j - T t=1 E(x a ) -ln(K) ≤ γ 2 /K 1 -γ T i=t E(x a ) - 1 K K i=1 x i + (e-2)γ 2 /K 2(1 -γ) T i=t E(x 2 a ) -2E(x a ) 1 K K i=1 x i + 1 K K i=1 x 2 i (19)
By definition, G max = max j T t=1 x j , EG alg = T t=1 E ∼p(t) (x a ), and

EG unif = T t=1 1 K K i=1 x i .
We can hence rewrite Equation ( 19) into:

G max -EG alg - K ln K γ ≤ γ 1 -γ (EG alg -EG unif ) + (e-2)γ 2(1 -γ) EG alg + EG unif -2 T t=1 K i=1 x i K E(x a ) (20)
Let ε be such that ∀i, t ε ≤ x i (t) then:

G max -EG alg ≤ K ln K γ + eγ 2(1 -γ) EG alg - (4-e + (e-2)ε)γ 2(1 -γ) EG unif (21) Assuming γ ≤ 1 2 : G max -EG alg ≤ K ln K γ + γ [eEG alg -(4-e + (e-2)ε) EG unif ] (22)
B.1. Proof of eq. ( 14)

For any j we have: W T +1 = K i=1 w i (T + 1) ≥ w j (T + 1). Hence:

W T +1 ≥ w j (T )e (γ/K)(ĉj (T )) = w j (T -1)e (γ/K)(ĉj (T -1)) e (γ/K)(ĉj (T )) = w j (1) T t=1 e (γ/K)(ĉj (t)) , and

ln W T +1 ≥ ln w j (1) + T t=1 γ K ĉj (t)
Since w j (1) = 1 for any j, it turns out that:

T t=1 γ K ĉj (t) -ln(K) ≤ ln( W T +1 W1 ) B.2. Proof of Lemma 1 ĉi (t) = i = a t ψ(x at -x bt ) 2p at (t) + i = b t ψ(x bt -x at ) 2p bt (t) E (a,b)∼p(t) ĉi (t) = K j=1 K k=1 p j (t)p k (t) i = j ψ(x j -x k ) 2p j + i = k ψ(x k -x j ) 2p k = K j=1 K k=1 p j p k i = j ψ(x j -x k ) 2p j + K j=1 K k=1 p j p k i = k ψ(x k -x j ) 2p k = 1 2 K k=1 p k ψ(x i -x k ) + 1 2 K j=1 p j ψ(x i -x j ) = E a∼p ψ(x i -x a )
If ψ(x) = x it simplifies into:

E (a,b)∼p(t) ĉi (t) = x i -E a∼p(t) x a B.
3. Proof of eq. ( 10) and ( 18)

M 2 = 1 K K i=1 p i (t)ĉ i (t) 2 = 1 K K i=1 p i i = a x a -x b 2p a + i = b x b -x a 2p b 2 = 1 K K i=1     p i i = a (x a -x b ) 2 4p 2 a + p i (t) i = b (x b -x a ) 2 4p 2 b + 2p i i = a i = b x a -x b 2p a x b -x a 2p b =0     = K i=1 p i i = a (x a -x b ) 2 4Kp 2 a + K i=1 p i i = b (x b -x a ) 2 4Kp 2 b = (x a -x b ) 2 4Kp a + (x b -x a ) 2 4Kp b = (p a + p b )(x a -x b ) 2 4Kp a p b E (a,b)∼p(t) M 2 = E (a,b)∼p(t) (p a + p b )(x a -x b ) 2 4Kp a p b = K i=1 K j=1 p i p j (p i + p j )(x i -x j ) 2 4Kp i p j = 1 4K K i=1 K j=1 (p i + p j )(x i -x j ) 2 = 1 4K K i=1 K j=1 (p i + p j )(x 2 i -2x i x j + x 2 j ) = 1 4K   K i=1 K j=1 p i x 2 i -2 K i=1 K j=1 p i x i x j + K i=1 K j=1 p i x 2 j + K i=1 K j=1 p j x 2 i -2 K i=1 K j=1 p j x i x j + K i=1 K j=1 p j x 2 j   = 1 4K 2KE(x 2 a ) -4E(x a ) K i=1 x i + 2 K i=1 x 2 i = 1 2 E a∼p(t) (x 2 a ) -2E a∼p(t) (x a ) 1 K K i=1 x i + 1 K K i=1 x 2 i For any x ∈ [0, 1], x 2 < x, hence: E (a,b)∼p(t) M 2 ≤ 1 2 E a∼p(t) (x a ) -2E a∼p(t) (x a ) 1 K K i=1 x i + 1 K K i=1 x i

C. Further Experiments

We give here the simulation results that could not fit on the core article: Figure 4 gives results for smaller number of rankers on NP2004 dataset and Figure 5 complete the experiments on MSLR30K dataset. On Figure 6 we added an experiment we made with Sparring coupled with UCB. We also considered two artificial matrices: SAVAGE and BVS. The 30×30 SAVAGE matrix, defined by P i,j = 1 2 + j/(2K) for i < j as described in [START_REF] Urvoy | Generic exploration and K-armed voting bandits[END_REF]. The 20×20 BVS matrix is defined by: P 1,j = 0.51 for any j > 1 and P i,j = 1 for any 1 < i < j. Its Condorcet winner has a low Borda score (9.69 against 18.49 for the Borda winner) which makes it difficult for algorithms to find the real Condorcet winner. These experiments results are sumarized in Figure 7. The preference matrices we used and their properties are summarized on Table 2. We conclude these experiments by a non-stationnary utility-based dueling bandit simulation where the expected reward gap ∆(t) between the best arm and the others is set in order to decieve stochastic algorithms (see Figure 8). There is no Condorcet winner on the left-hand-side informational queries matrix (we took a Copeland winner as a placeholder but the regret is negative for some arms). ∼ O KT • log(T ) . To ease reading we provide the same plot with logarithmic scale on the left and linear scale on the right.

Relative Exponential Weighing for Dueling Bandits (extended version) [START_REF] Yue | Beat the mean bandit[END_REF] parameter.

In that case: γ ≥ 1 γ *

Optimal γ as defined in (6) α

Input parameter in RUCB (Zoghi et al., 2014a) α >

Figure 1 .

 1 Figure 1. Empirical validation of Corollary 1. The colored areas around the curves show the minimal and maximal values over 100 runs.

Figure 2 .Figure 3 .

 23 Figure2. Regret and accuracy plots averaged over 100 runs (50 runs for fixed-horizon algorithms) respectively on ARXIV dataset (6 rankers) and LETOR NP2004 dataset (64 rankers). On regret plots, both time and regret scales are logarithmic ( √ t hence appears as t/2). The colored areas around the curves show the minimal and maximal values over the runs.

Figure 4 .

 4 Figure4. Average regret and accuracy plots on LETOR NP2004 with respectively 16, and 32 rankers. We also give the anytime runs for BTM and SAVAGE with a conservative δ = 10 -8 . On regret plots, both time and regret scales are logarithmic ( √ t hence appears as t/2). The colored areas around the curves show the minimal and maximal values over the runs.

Figure 5 .

 5 Figure 5. Expected regret and accuracy plots on MSLR30K with respectively informational and perfect navigational queries (136 rankers).There is no Condorcet winner on the left-hand-side informational queries matrix (we took a Copeland winner as a placeholder but the regret is negative for some arms).

Figure 6 .

 6 Figure 6. Average regret and accuracy plots respectively on LETOR NP2004 (64 rankers) and MSLR30K navigational queries (136 rankers) with Sparring coupled with a standard UCB MAB.

Figure 7 .

 7 Figure 7. Average regret and accuracy plots respectively on SAVAGE and BVS artificial matrices.

Figure 8 .

 8 Figure 8. In this plot, we experiment a synthetic utility-based 10-armed bandits problem with non-stationary rewards. The rewards are taken from Bernoulli distributions. The best arm has a time-dependent expected reward equal to 1/2 + ∆(t) with ∆(t) = K • log(t)/t. The others arms' rewards are stationary with a mean of 1/2. The gap function ∆(t) has been chosen to deceive stochastic algorithms: O K•log(T ) ∆(T )

Table 1 .

 1 Notation table

	Notation	Description

Table 2 .

 2 1 2 a t , b t or a, b Pulled arms at time t i, j, k Reserved for (fixed) arms indices P Preference matrix P i,jThe probability of arm i winning against arm j r a,bCondorcet regret (2) incurred when arms a and b are pulled x a (t) or x a Reward/utility of arm a t drawn at time instant t x(t) Vector containing rewards of all K arms at time tx(t) = (x 1 (t), . . . , x K (t)) v iProbability distribution associated with arm i For stochastic modelsµ i Mean of probability distribution v i µ i = E ∼vi x i µ Mean reward vector µ = (µ 1 , . . . , µ K ) r a,b (t)Bandit regret (3) incurred at time instant t when arms a and b are pulled. On stochastic settings:Er a,b (t) = 2r a,b . . . Feedback transfer function ψ(x ax b ) = x ax b or ψ(x ax b ) = x a ≥ x b w i (t)or w i EXP3 weight of arm i at time t W t Sum of weights at time t W t = i w i (t) p i (t) EXP3 probablity that arm i is pulled at time t p(t) Probablity distribution containing p(t) = (p 1 (t), . . . , p K (t)) ĉi (t) EXP3 regret estimator as defined in (5) G max Maximum possible gain for a single-arm strategy G alg Gain earned due to the strategy of alg EG unifGain earned due to the uniform strategy EG unif = 1 Some preference matrices we used.

		Indicator function
	i K	t	i x i (t)
	G min	Minimum possible gain for a single-arm strategy
	M 1 , M 2	See (11)
	L H K	Partial monitoring Loss matrix Partial monitoring Feedback matrix FEEDEXP3 transfer matrix

* Optimal arm index: Copeland/Condorcet winner of preference matrix i * ∈ arg max K j=1 P i,j > 1 2 For utility based statement: i * ∈ arg max µ i ψ

Note that we frequently drop the time index when it is unnecessary or clear from context. For instance we simply write xa(t) or simply xa instead of xa t (t).

Acknowledgments

We would like to thank the reviewers for their constructive comments and Masrour Zoghi who kindly sent us his experiment datasets.