# Rethinking Evaluation Metric for Probability Estimation Models Using Esports
Data

Euihyeon Choi  PS Analytics
Seoul, South Korea
<EMAIL_ADDRESS>Jooyoung Kim  SK Holdings C&C
Seongnam, South Korea
<EMAIL_ADDRESS>Wonkyung Lee  PS Analytics
Seoul, South Korea
<EMAIL_ADDRESS>
###### Abstract

Probability estimation models play an important role in various fields, such
as weather forecasting, recommendation systems, and sports analysis. Among
several models estimating probabilities, it is difficult to evaluate which
model gives reliable probabilities since the ground-truth probabilities are
not available. The win probability estimation model for esports, which
calculates the win probability under a certain game state, is also one of the
fields being actively studied in probability estimation. However, most of the
previous works evaluated their models using accuracy, a metric that only can
measure the performance of discrimination. In this work, we firstly
investigate the Brier score and the Expected Calibration Error ($ECE$) as a
replacement of accuracy used as a performance evaluation metric for win
probability estimation models in esports field. Based on the analysis, we
propose a novel metric called Balance score which is a simple yet effective
metric in terms of six good properties that probability estimation metric
should have. Under the general condition, we also found that the Balance score
can be an effective approximation of the true expected calibration error which
has been imperfectly approximated by $ECE$ using the binning technique.
Extensive evaluations using simulation studies and real game snapshot data
demonstrate the promising potential to adopt the proposed metric not only for
the win probability estimation model for esports but also for evaluating
general probability estimation models.

###### Index Terms:

Probability Estimation, Calibration, $ECE$, Balance Score

##  I Introduction

Probability estimation problem is already an important issue in various
fields, such as weather forecasting [1], recommendation systems [2], and
sports analysis [3, 4]. Since reliable probability in such fields brings great
benefits to our life [5], various models have been proposed to estimate the
reliable probability. However, unlike classification problems with true
labels, the probability estimation problem is more difficult to evaluate
because there is no ground-truth $p$ label [6]. It is thus increasingly
important to select a metric carefully to measure the performance of
probability estimation models adequately. As an option of the probability
estimation evaluation metric, several works have been done to develop metrics
such as the Brier score [7] and the Expected Calibration Error ($ECE$) [8]
which are proposed to measure the calibration performance of models instead of
accuracy.

Recently with the rapid market growth of esports, research to apply the win
probability estimation model to the esports field is also being actively
conducted [9, 10]. Among the esports genres, the multiplayer online battle
arena (MOBA) genre is one of the main targets to apply the win probability
estimation model based on its high market share in the esports field and also
easily accessible data to train the models [10]. To the best of our knowledge,
however, most of the previous works on the MOBA genre are still using accuracy
as a metric in the evaluation of their probability estimation models.
Unfortunately in the esports field, using accuracy as an evaluation metric can
be more unstable since the datasets in esports have a huge diversity [9] in
terms of _operating conditions_ (the distribution of ground-truth $p$) which
the probability estimation model works with. In classic sports, the aspect of
the game does not differ significantly depending on the point of view of the
game. However in MOBA, the aspect of the game is very different at each point
of the game, as the stats of the characters played by each human player change
dynamically within the game. This makes the operating condition of datasets
completely distinct at each time point. In addition, repeated updates by game
companies make another diversity to the operating condition of datasets by
changing the dynamics of the game. It is concluded that research on the win
probability estimation model using esports data are being conducted on very
different datasets without a fixed dataset. These circumstances make that the
suggested model cannot guarantee performance in other cases.

In this work, we provide a detailed analysis of three candidate metrics that
can be employed to evaluate probability estimation models for esports data.
Based on the analysis of candidate metrics, we propose a simple yet effective
evaluation metric called Balance score that can address the shortcomings
identified in other metrics. Extensive evaluation using simulation studies and
real game snapshot data verifies the benefits of the proposed metric and opens
up possibilities to be utilized in general probability estimation model.

Figure 1: Problem of using accuracy as a measure of probability estimation
models in esports. Compare to the image classification task which only ask for
the label, even the optimal model may not be able to estimate the result of
the match due to the uncertainty of the game snapshot data itself.

##  II Related Works & Proposed Metric

###  II-A Overview

Most previous studies on win probability estimation models in esports use
accuracy as an evaluation metric [9, 10]. However, accuracy is a metric that
only measures the discrimination performance of the model, so it does not
guarantee the performance of the model on estimating the exact win probability
[8]. Also, in general classification tasks such as image classification,
training is carried out assuming that the optimal model will show optimal
performance (e.g., 100%). However, in the game snapshot data problem, it can
be seen that even the optimal model cannot achieve 100% accuracy due to the
uncertainty of the game snapshot data itself as shown in Fig. 1. Compare to
the evaluation of a classification problem that can be measured with a given
ground-truth label, proper evaluation of the probability estimation model is
more challenging because the ground-truth probability is unknown.

Recently in fields other than esports, two representative works namely, the
Brier score [7] and the Expected Calibration Error ($ECE$) [8] are proposed to
measure the calibration performance of models instead of accuracy. Calibration
refers to the statistical consistency between the estimated probabilities and
the true results. Unlike accuracy, measuring the calibration performance thus
can reflect the estimated probability values.

In this section, we firstly formulate win probability estimation problem in
the esports field. Subsequently, we introduce two representative metrics for
calibration performance measures based on their definitions, advantages, and
disadvantages. Finally, we propose a novel metric called Balance score
motivated by two metrics.

###  II-B Problem Formulation

Assume the game snapshot dataset consists of feature vectors $\bm{x_{i}},1\leq
i\leq n$, and their corresponding results $y_{i}\in\mbox{ }\\{0,1\\}$. For $n$
game snapshots, each feature vector can consist of several scalar information
at the time (e.g., earned gold, earned experience points) depending on the
game to measure. Following, the ‘0’ and ‘1’ for the result $y_{i}$
respectively refers to the ‘lose’ and ‘win’ at the end of the game.

Given a win probability estimation model, the model predicts the win
probability $\hat{p_{i}}$ of each snapshot $\bm{x_{i}}$. Noting that the real
win probability $p_{i}$ of the snapshot is unknown. The purpose of the
evaluation metric for the win probability estimation model is thus to
adequately evaluate the model’s predicted output $\hat{p}$ of each game
snapshot.

###  II-C Brier Score

Scoring function is a set of rules that involves computation between the
estimated probability and the actual outcome. Scoring function can be used to
evaluate the estimated probabilities and encourage models to estimate ‘good’
probabilities by providing the appropriate score [11]. For each snapshot
$\bm{x_{i}}$, only $\hat{p_{i}}$ and $y_{i}$ are used as input of scoring
function since $p_{i}$ is unknown. The Brier score is one of the
representative scoring rules which has been normally used to evaluate the
probability estimation models. The Brier score can be represented with its
scoring function $f_{br}(\cdot)$ and expectation as follows:

$Brier\mbox{ }score=\frac{1}{n}\sum_{i=1}^{n}f_{br}(\hat{p_{i}},y_{i}),$ (1)

where

$f_{br}(\hat{p_{i}},y_{i})=(\hat{p_{i}}-y_{i})^{2}.$ (2)

Equation (1) can be decomposed again into two terms as follows [12]:

$\begin{split}Brier\mbox{
}score=\frac{1}{n}\sum_{i=1}^{n}(\hat{p_{i}}-y_{i})(2\hat{p_{i}}-1)+\frac{1}{n}\sum_{i=1}^{n}\hat{p_{i}}(1-\hat{p_{i}}).\end{split}$
(3)

In equation (3), the left term falls into 0 in expectation under the perfect
calibration while the right term related to the sharpness, the concentration
of the predictive distribution [13]. This means that the Brier score
simultaneously addresses the calibration performance and the sharpness of
probability estimation. Also, the Brier score is one of the strictly proper
scoring rules [14] which have the characteristic that estimating $\hat{p_{i}}$
to $p_{i}$ is the only optimal strategy for the expected score. In general,
the expected score of a model under a certain scoring function can be
calculated as:

$\begin{split}{\mathbb{E}_{model}}[score]&=\int_{0}^{1}\int_{0}^{1}\left[p\cdot
f(\hat{p},1)+(1-p)\cdot f(\hat{p},0)\right]\\\
&\quad\times{P_{model}}(\hat{p}|p)d\hat{p}\,\pi(p)dp\end{split}$ (4)

where $f(\hat{p},y)$, $\pi(p)$ and $P_{model}(\hat{p}|p)$ respectively denotes
the scoring function, the distribution of the ground-truth $p$ on target
dataset, and the conditional probability of $\hat{p}$ under $p$ of the model.

An optimal model which always gets $\hat{p_{i}}=p_{i}$ can also be evaluated
in terms of the Brier score. Assume a situation where the optimal model gets
scores with uniform distribution of the ground-truth $p$(i.e., $\pi(p)=1$ for
0 $\leq p\leq 1$, $\pi(p)=0$ otherwise). In the case of esports, it can be
seen as an example of win probability estimation in the middle of a match
where the win probability is likely to be uniformly distributed rather than
concentrated. In such conditions, optimal expected scores of accuracy (which
also can be represented as a scoring function) and the Brier score can be
calculated as 0.75 (75%) and 0.166 respectively, according to the equation
(4). Since the operating condition of a specific dataset is unknown in real
cases, the optimal score which can be the target is also unknown. It means
that the low Brier score reported in previous studies cannot guarantee general
performance. Instead, the score can only be used as a relative measure of
multiple models for a single fixed dataset that shares an operating condition.
This limitation of the Brier score can be a major drawback to its adoption as
a metric in the field of esports which does not have a fixed dataset and the
operating condition varies widely each time.

###  II-D Expected Calibration Error

In recent studies, several approaches such as the reliability diagram [15],
Expected Calibration Error ($ECE$), and Maximum Calibration Error ($MCE$) [8]
have been proposed to measure the calibration performance of a model. Among
these metrics, $ECE$ is frequently used because it can reasonably express the
calibration performance of the model with a single scalar value. The perfect
calibration from the model can be expressed as follows:

$Prob(\hat{Y}=1|\hat{P}=p)=p,\forall p\in[0,1].$ (5)

Then, the model’s true expected calibration error is represented as follows:

$\mbox{True
ECE}=\underset{\hat{P}}{\mathbb{E}}[|Prob(\hat{Y}=1|\hat{P}=p)-p|].$ (6)

To approximate the true expected calibration error, Guo et al. [16] suggested
dividing the set of $\hat{p_{i}}$ with [0, 1] probability interval into $M$
equally spaced bins. $ECE$ value is calculated based on the errors from these
bins as follows:

$ECE=\sum_{m=1}^{M}\frac{|B_{m}|}{n}|\overline{y}(B_{m})-\overline{\hat{p}}(B_{m})|,$
(7)

where $B_{m}$ denotes the set of indices of predictions belonging to m-th bin,
$\overline{y}(B_{m})$ denotes the proportion of the true results of
predictions in m-th bin, and $\overline{\hat{p}}(B_{m})$ denotes the average
of probability predictions in m-th bin. Noting here the term ‘$ECE$’ refers to
the approximation of the true expected calibration error (True ECE) by
equation (7) hereafter. Compare to accuracy and the Brier score, an optimal
model which always predicts $p_{i}$ as $p_{i}$ can get 0 $ECE$ value. Knowing
the optimal value has the advantage that the model experimenter can check
whether the model approaches perfect calibration by tracking the $ECE$ value
of the model [16].

However, $ECE$ has some limitations. First of all, there is no criterion for
determining how many bins to divide. To get a precise approximation of the
true expected calibration error, a larger $M$ would be better. However, if $M$
is increased, the number of $\hat{p_{i}}$ in each bin decreases which results
in a large bias in the $ECE$ value [17]. If the calibration performance of
several models on one dataset is compared, the order of the calibration
performance of the models can be changed as the $M$ value is changed. Also,
due to the nature of the calibration metric which divides bins and collects
predictions to calculate values, only evaluations on the entire dataset are
possible. Based on these observations, we propose a scoring function based
metric called Balance score which addresses the shortcomings of existing
metrics and takes only their advantages.

###  II-E Balance Score

The Balance score is a score with gain and loss strategy, which pursues the
balance of the score. If model predicts the true observation $y_{i}$ based on
$\hat{p_{i}}$, it gains a score and if it predicts incorrectly, it loses a
score. For each $\bm{x_{i}}$ which is difficult to predict the result
correctly (e.g., $p$ in 40% $\sim$ 60%), a large score is gained if the
predicted result is correct, and a small score is lost if the predicted result
is incorrect. Conversely, when $\bm{x_{i}}$ is easy to predict the result
correctly (e.g., $p$ close to 0% or 100%), a small score is gained if the
predicted result is correct, and a large score is lost if the predicted result
is incorrect. The Balance score with its scoring function $f_{ba}(\cdot)$ can
be defined as follows:

$f_{ba}(\hat{p_{i}},y_{i})=\begin{cases}1-\hat{p_{i}},&\mbox{if
}\hat{p_{i}}\geq 0.5\mbox{ and }y_{i}=1\\\ \hat{p_{i}},&\mbox{if
}\hat{p_{i}}<0.5\mbox{ and }y_{i}=0\\\ -\hat{p_{i}},&\mbox{if }\hat{p_{i}}\geq
0.5\mbox{ and }y_{i}=0\\\ -1+\hat{p_{i}},&\mbox{if }\hat{p_{i}}<0.5\mbox{ and
}y_{i}=1\end{cases},$ (8) $Balance\mbox{
}score=\frac{1}{n}\sum_{i=1}^{n}f_{ba}(\hat{p_{i}},y_{i}).$ (9)

To give new properties of the Balance score, let $G(p)$ be the pointwise
expected score when model predicts $p$ as $p$. Then the model can get 0 score
by maintaining the total score to be balanced as follows:

$\begin{split}G(p)&=pf_{ba}(p,1)+(1-p)f_{ba}(p,0)\\\ &=0\text{ for }\forall
p\in[0,1].\end{split}$ (10)

Also, when $p$ is estimated to be a different value, the balance is broken in
proportion to the difference between $p$ and the estimated value. More
generally, let $g(q;p)$ be the pointwise expected score function when model
predicts $q$ under the ground-truth probability $p$. Then $G(p)=g(p;p)$ holds.
Also, the following expression holds:

$|g(q;p)|=|q-p|\text{ for }\forall q,p\in[0,1].$ (11)

Equation (11) simply shows that model gets 0 score only if model estimates $p$
under $p$, and the balance is broken in proportion to the difference. The
Balance score is not following the proper scoring rule suggested in [14]
because it is a new scoring rule with gain and loss. However, the Balance
score still shares the concept of a proper scoring rule that estimating $p$ as
$p$ is the optimal strategy for the expected score.

An expected score of the Balance score can also be calculated with equation
(4). Same with the $ECE$, the optimal model also can get 0 value according to
equation (10) regardless of the operating condition. This means that the
optimal Balance score can be the target of models to be trained. Moreover,
recent machine learning models suffer mainly from overconfidence or
underconfidence in terms of probability estimation [16]. According to the
tendency of the model, if a extreme prediction $\hat{p_{i}}$ close to 0 or 1
is given compared to the actual $p_{i}$, it is called overconfident, and if it
is given a mild value, it is called underconfident. Assume a situation with
$Prob(\hat{Y}=1|\hat{P}=p)=q_{p}$. If a model has an overconfident property,
$p$ is placed in $0.5\leq p\leq q_{p}\mbox{ for }0.5\leq p$ and $q_{p}\leq
p<0.5\mbox{ for }p<0.5$. Then true expected calibration error is approximated
as:

True ECE $\displaystyle=$
$\displaystyle\underset{\hat{P}}{\mathbb{E}}[|Prob(\hat{Y}=1|\hat{P}=p)-p|]$
$\displaystyle=$ $\displaystyle\underset{\hat{P}}{\mathbb{E}}[|q_{p}-p|]$
$\displaystyle=$
$\displaystyle\underset{\hat{P}<0.5}{\mathbb{E}}[p-q_{p}]+\underset{0.5\leq\hat{P}}{\mathbb{E}}[q_{p}-p]$
$\displaystyle=$
$\displaystyle\underset{\hat{P}<0.5}{\mathbb{E}}[-g(q_{p};p)]+\underset{0.5\leq\hat{P}}{\mathbb{E}}[-g(q_{p};p)]$
$\displaystyle=$ $\displaystyle-\underset{\hat{P}}{\mathbb{E}}[g(q_{p};p)]$
$\displaystyle\approx$ $\displaystyle-Balance\mbox{ }score.$

Conversely, if model has an underconfident property, $\mbox{True ECE}\approx
Balance\mbox{ }score$. This means that the Balance score is another
approximation of true expected calibration error under general condition, but
without binning technique. To conclude, Table I summarizes whether the metrics
have good properties as probability estimation metric.

TABLE I: A summary of the candidate metrics for evaluating probability estimation models. Properties | Accuracy | Brier score | ECE | Balance score
---|---|---|---|---
Correctly estimating $p$ is its optimal strategy | $\circ$ | $\circ$ | $\circ$ | $\circ$
Can evaluate a single estimation | $\circ$ | $\circ$ | $\times$ | $\circ$
The optimal value is given | $\times$ | $\times$ | $\circ$ | $\circ$
Can be an absolute measure | $\times$ | $\times$ | $\circ$ | $\circ$
Do not have hyperparameter | $\circ$ | $\circ$ | $\times$ | $\circ$
Is a calibration measure | $\times$ | $\circ$ | $\circ$ | $\circ$

##  III Empirical Results

In this section, we evaluate the proposed evaluation metric using simulation
studies and real game snapshot data. Under the first case study, we evaluate
the expected accuracy, Brier score, $ECE$, and Balance score obtained from the
optimal model under various beta distributions. The expected scores obtained
from the logistic regression model under real game snapshot datasets at
different time points are also evaluated to show the limitations of accuracy
and the Brier score. In the second case study, we compare two calibration
based metrics ($ECE$, Balance score) in detail.

###  III-A Case Study I: Limitations of accuracy and Brier score

In equation (4), an analytical method to calculate the expected score of a
model under a specific operating condition and a specific scoring function was
presented. Assume a situation in which a model was scored on a dataset
following a specific distribution. This is done by repeating the situation
where $p_{*}$ is firstly generated following a specific distribution, $y_{*}$
is determined according to the value of $p_{*}$, and assume the model
estimates it to $\hat{p_{*}}$. Since each $p_{*}$ exists between [0,1] and the
conditions of the two competing teams are the same, the win probability
distribution of the game snapshot dataset can be considered to follow a
symmetric beta distribution with an average win probability of 0.5 (50%). The
win probability distribution of the game state snapshot dataset is very
different depending on the state of the game. At the beginning of the game,
the odds of the two competing teams are not significantly different, so the
win probabilities will be concentrated near 50%. As time goes by, the tail of
the distribution will become thicker, and the distribution of the win
probability will lean to both extreme sides after the middle of the game. This
situation can be simulated by adjusting the $\alpha$ and the $\beta$
parameters of the beta distribution.

As a simulation study, The upper row of the Table II summarizes expected
accuracy, Brier score, $ECE$, and Balance score of the optimal model on
dataset with the distribution of probabilities following $Beta(0.5,0.5)$,
$Beta(1,1)$, and $Beta(2,2)$. By generating 100,000 synthetic data $p_{*}$
following each distribution, the score can be calculated according to the
simulation method which becomes the approximation of the equation (4). The
number of bin $M$ for $ECE$ is set to 10 and subsequently calculated by
collecting pairs of ($\hat{p_{*}}$, $y_{*}$).

As shown in the upper row of the Table II, the optimal model cannot achieve
100% accuracy, and the optimal accuracy value varies greatly depending on the
distribution, from 68.92% to 81.88%. Similar to the accuracy, the Brier score
also differs greatly depending on the distribution (0.1995 to 0.1241). Also,
the true $p$ and the true distribution of $p$ of actual dataset are unknown as
mentioned in the previous section. Therefore, the result of achieving a
certain accuracy and Brier score in a certain dataset cannot be a general
performance. Since the true ECE of the optimal model is 0, both the $ECE$ and
the Balance score properly approximate them to 0 regardless of the
distribution of $p_{*}$. Noting that the error of $ECE$ is slightly larger
than the Balance score due to the bias caused by the binning process.

For the experiment of real game snapshot data, the game snapshot data from the
“League of Legends”, one of the popular MOBA games is collected through the
Riot Games public API [18] and evaluated. We collected datasets at three
different time points which are expected to follow the three distributions
assumed in the simulation study. The feature vector $x_{*}$ for each snapshot
data is generated by taking 14 indicators that affect the winning of the match
(the gold difference for each role player (5), the experience difference for
each role player (5), the number of killed dragons for each team (2), and the
number of destroyed towers for each team (2) similar to that in [19].
Following our problem formulation, their corresponding results $y_{*}$ are
also recorded as the true labels. For each time point, 100,000 matches were
taken and vectorized, while 60,000 matches were allocated as a training set
and the remaining 40,000 matches were allocated as a testset. The lower row of
the Table II shows the results calculated by each metric after the learning
with a logistic regression model that naturally derives probabilities. The
distribution of $\hat{p}$ derived by the logistic regression model trained
with the dataset for each time period is shown in Fig. 2. As shown in the
figure, the game snapshots at 5, 10, and 15 minutes respectively resemble the
distributions of $Beta(2,2)$, $Beta(1,1)$, and $Beta(0.5,0.5)$.

Figure 2: Three plots in left side respectively refers to the plot of $p$ obtained from the generated beta distributions $Beta(2,2)$, $Beta(1,1)$, and $Beta(0.5,0.5)$. Distributions of $\hat{p}$ derived by the logistic regression model trained with the real game snapshot datasets at 5, 10, and 15 minutes are also plotted on the right side. TABLE II: Expected scores obtained from the optimal model (under beta distributions) and the logistic regression model (for each time point). Distributions & Time points | Accuracy | Brier | $ECE$ | Balance
---|---|---|---|---
$Beta(0.5,0.5)$ | 81.88% | 0.1241 | 0.0019 | 0.0000
$Beta(1,1)$ | 75.01% | 0.1666 | 0.0017 | -0.0004
$Beta(2,2)$ | 68.92% | 0.1995 | 0.0031 | 0.0013
15 min | 79.84% | 0.1385 | 0.0078 | -0.0039
10 min | 73.55% | 0.1755 | 0.0068 | -0.0016
5 min | 65.56% | 0.2159 | 0.0058 | 0.0043

Consider the distributions of $\hat{p}$ from the trained model are similar to
the assumed distributions of $p$ and the scores from the trained model are
similar to the optimal model’s score. Based on the results in the Table II,
the trained logistic regression model can be considered a pretty nice model.
However, the low accuracy of 65.56% can be considered that the model’s
discrimination power is insufficient. In a similar manner, the high Brier
score of 0.2159 may seem insufficient to use the logistic regression model as
a probability estimation model. For this gap between the understandings of the
model’s performance, it would be right to understand that the performance is
limited by the uncertainty of the data rather than conclude that the logistic
regression model does not have sufficient capacity or that there is a learning
problem. However, since the distribution of true $p$ is unknown and
subjective, comparing the performance with that of the optimal score on the
assumed distribution is also not reasonable. Instead, the $ECE$ or the Balance
score has a chance to be an absolute measure of the model’s performance which
also measures the calibration performance of the model. Since we know that the
optimal value of both metrics is 0, we can directly understand the performance
of the logistic regression model itself and thus can target to update the
model targeting the values to be 0.

###  III-B Case Study II: Comparison between $ECE$ and Balance score

$ECE$, one of the best choices for approximating the true ECE, involves a
binning process (see equation (7)). The binning hyperparameter $M$ should be
increased to make the approximation more accurate, but the bias occurs because
the number of $\hat{p_{*}}$ in each bin decreases.

To illustrate limitations of a binning process for performance evaluation
task, we assume two synthetic models with some degree of overconfident
tendency. These models tend to overestimate for each true $p$. When the
tendency is 0.1, the degree is about 1/10 of the model that is completely
overconfident and estimates 0 or 1 for all $p$. For example, the model
estimates $0.9*0.6+0.1*1=0.64$ for true $p$ of 0.6, and $0.9*0.2+0.1*0=0.18$
for true $p$ of 0.2. Fig. 3 shows the resultant $ECE$ values along the
increasing $M$ from 5 to 100 with 10,000 ($\hat{p_{*}}$, $y_{*}$) pairs
obtained from the synthetic models with a tendency of 0.1 and 0.11. The
corresponding 10,000 true $p_{*}$ are generated from the uniform distribution.
Since the true ECE of the model with tendency 0.1 is smaller than the model
with tendency 0.11, it is clear that the $ECE$ value also should be smaller.
However, depending on the selection of $M$, $ECE$ of the model with a tendency
of 0.11 can be smaller than the model with a tendency of 0.1 as shown in the
crossing points of blue and red lines in Fig. 3. This shows that the order of
the models’ performance can be changed by the subjective choice of the
experimenter regardless of their actual performance. Instead, the Balance
score can be an exact measure for the performance evaluation of the model
without any hyperparameter.

Figure 3: $ECE$ values with increasing binning number $M$ and the absolute
Balance score of two overconfident models. Red lines with circle markers and
asterisk markers respectively refers to the $ECE$ of the model with 0.1 and
0.11 tendency. Blue dashed line and dash-dotted line respectively refers to
the absolute Balance score of the model with 0.1 and 0.11 tendency.

In addition, the Balance score also requires much fewer data to estimate the
true ECE based on pointwise calculation. When the distribution of $p_{*}$ is
uniform, the analytic solution of the true ECE for an overconfident model with
a tendency of 0.1 can be calculated to 0.025 following the equation (6). Fig.
4 shows the $ECE$ ($M=10$) and the Balance score of the model along the
increment of utilized synthetic data size from 50 to 1000. Compare to the
$ECE$ which needs more than 500 sample data to approximate the true ECE, the
Balance score can approach the true ECE value with much fewer data. Note that
the pointwise calculation of the Balance score also resulted in the
computational efficiency compared to the $ECE$ calculation. Based on the
observations, the Balance score without a subjective binning process shows
several advantages over the $ECE$ in terms of evaluation metric.

Figure 4: $ECE$ and the absolute Balance score of overconfident model with 0.1
tendency over the increasing data size. The red line with asterisk markers and
the blue line with circle markers respectively refers to $ECE$ and Balance
score while the green dashed line denotes the analytic true ECE value of the
evaluated model.

##  IV Conclusion

In this work, we have investigated how to adequately evaluate probability
estimation models via esports’ win probability estimation model. Through the
theoretical analysis and experiments, we found that a novel metric called
Balance score, motivated by the Brier score and $ECE$, takes the advantages of
existing metrics and also solves their shortcomings. Also, under machine
learning models’ general condition, we found that the Balance score can be an
effective approximation of the true expected calibration error.

In future works, we expect to develop a model that provides more reliable
probabilities for esports’ win probability with the help of proper evaluation
by the Balance score. Additionally, we will investigate favorable effects of
replacing $ECE$ in various calibration-involved areas such as calibrated model
learning and post-processing calibration methods.

## References

  * [1] S. Agrawal, L. Barrington, C. Bromberg, J. Burge, C. Gazen, and J. Hickey, “Machine learning for precipitation nowcasting from radar images,” 2019. [Online]. Available: https://arxiv.org/abs/1912.12132
  * [2] W. Kweon, S. Kang, and H. Yu, “Obtaining calibrated probabilities with personalized ranking models,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 36, no. 4, 2022, pp. 4083–4091.
  * [3] D. Lock and D. Nettleton, “Using random forests to estimate win probability before each play of an nfl game,” _Journal of Quantitative Analysis in Sports_ , vol. 10, no. 2, pp. 197–205, 2014.
  * [4] P. Robberechts, J. Van Haaren, and J. Davis, “A bayesian approach to in-game win probability in soccer,” in _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, 2021, pp. 3512–3521.
  * [5] B. Zadrozny and C. Elkan, “Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers,” in _International conference on machine learning_ , 2001, pp. 609–616.
  * [6] S. Liu, A. Kaku, W. Zhu, M. Leibovich, S. Mohan, B. Yu, H. Huang, L. Zanna, N. Razavian, J. Niles-Weed, and C. Fernandez-Granda, “Deep probability estimation,” 2021. [Online]. Available: https://arxiv.org/abs/2111.10734
  * [7] G. W. Brier _et al._ , “Verification of forecasts expressed in terms of probability,” _Monthly weather review_ , vol. 78, no. 1, pp. 1–3, 1950.
  * [8] M. P. Naeini, G. Cooper, and M. Hauskrecht, “Obtaining well calibrated probabilities using bayesian binning,” in _Twenty-Ninth AAAI Conference on Artificial Intelligence_ , 2015.
  * [9] V. J. Hodge, S. Devlin, N. Sephton, F. Block, P. I. Cowling, and A. Drachen, “Win prediction in multiplayer esports: Live professional match prediction,” _IEEE Transactions on Games_ , vol. 13, no. 4, pp. 368–379, 2019.
  * [10] Z. Yang, Z. Pan, Y. Wang, D. Cai, S. Shi, S.-L. Huang, W. Bi, and X. Liu, “Interpretable real-time win prediction for honor of kings–a popular mobile moba esport,” _IEEE Transactions on Games_ , 2022.
  * [11] R. L. Winkler, J. Munoz, J. L. Cervera, J. M. Bernardo, G. Blattenberger, J. B. Kadane, D. V. Lindley, A. H. Murphy, R. M. Oliver, and D. Ríos-Insua, “Scoring rules and the evaluation of probabilities,” _Test_ , vol. 5, no. 1, pp. 1–60, 1996.
  * [12] K. Rufibach, “Use of brier score to assess binary predictions,” _Journal of clinical epidemiology_ , vol. 63, no. 8, pp. 938–939, 2010.
  * [13] T. Gneiting and A. E. Raftery, “Strictly proper scoring rules, prediction, and estimation,” _Journal of the American statistical Association_ , vol. 102, no. 477, pp. 359–378, 2007.
  * [14] M. J. Schervish, “A general method for comparing probability assessors,” _The annals of statistics_ , vol. 17, no. 4, pp. 1856–1879, 1989.
  * [15] M. H. DeGroot and S. E. Fienberg, “The comparison and evaluation of forecasters,” _Journal of the Royal Statistical Society: Series D (The Statistician)_ , vol. 32, no. 1-2, pp. 12–22, 1983.
  * [16] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger, “On calibration of modern neural networks,” in _International conference on machine learning_ , 2017, pp. 1321–1330.
  * [17] J. Nixon, M. W. Dusenberry, L. Zhang, G. Jerfel, and D. Tran, “Measuring calibration in deep learning.” in _CVPR Workshops_ , 2019.
  * [18] RiotGames, “Riot developer portal.” https://developer.riotgames.com/apis.
  * [19] P. Z. Maymin, “Smart kills and worthless deaths: esports analytics for league of legends,” _Journal of Quantitative Analysis in Sports_ , vol. 17, no. 1, pp. 11–27, 2021.


# Codebook Design and Beam Training for Extremely Large-Scale RIS: Far-Field
or Near-Field?

Xiuhong Wei, Linglong Dai, Yajun Zhao, Guanghui Yu, and Xiangyang Duan X. Wei
and L. Dai are with the Beijing National Research Center for Information
Science and Technology (BNRist) as well as the Department of Electronic
Engineering, Tsinghua University, Beijing 100084, China (e-mails:
<EMAIL_ADDRESS>daill@tsinghua.edu.cn).Y. Zhao, G. Yu, and X.
Duan are with the Wireless Pre-Research Department, ZTE Corporation, Shenzhen
518038, China (e-mail: {zhao.yajun1, yu.guanghui,
duan.xiangyang}@zte.com.cn).This work was supported in part by the National
Key Research and Development Program of China (Grant No. 2020YFB1807201) and
in part by the National Natural Science Foundation of China (Grant No.
62031019).

###### Abstract

Reconfigurable intelligent surface (RIS) can improve the capacity of the
wireless communication system by providing the extra link between the base
station (BS) and the user. In order to resist the “multiplicative fading”
effect, RIS is more likely to develop into extremely large-scale RIS (XL-RIS)
for future 6G communications. Beam training is an effective way to acquire
channel state information (CSI) for the XL-RIS assisted system. Existing beam
training schemes rely on the far-field codebook, which is designed based on
the far-field channel model. However, due to the large aperture of XL-RIS, the
user is more likely to be in the near-field region of XL-RIS. The far-field
codebook mismatches the near-field channel model. Thus, the existing far-field
beam training scheme will cause severe performance loss in the XL-RIS assisted
near-field communications. To solve this problem, we propose the efficient
near-field beam training schemes by designing the near-field codebook to match
the near-field channel model. Specifically, we firstly design the near-field
codebook by considering the near-field cascaded array steering vector of XL-
RIS. Then, the optimal codeword for XL-RIS is obtained by the exhausted
training procedure between the XL-RIS and the user. In order to reduce the
beam training overhead, we further design a hierarchical near-field codebook
and propose the corresponding hierarchical near-field beam training scheme,
where different levels of sub-codebooks are searched in turn with reduced
codebook size. Simulation results show the two proposed near-field beam
training schemes both perform better than the existing far-field beam training
scheme. Particulary, the hierarchical near-field beam training scheme can
greatly reduce the beam training overhead with acceptable performance loss.

###### Index Terms:

Extremely large-scale RIS, near-field codebook design, beam training.

##  I Introduction

Recently, reconfigurable intelligent surface (RIS) has been proposed to
improve the capacity of the wireless communication system [1]. Specifically,
RIS consists of a large number of reconfigurable elements (e.g., 256), which
can be deployed between the base station (BS) and the user to establish an
extra reflecting link. By properly reconfiguring the RIS elements, RIS can
provide high reflecting beamforming gain with low cost and low consumption
[2]. The reliable RIS reflecting beamforming requires the accurate channel
state information (CSI) [3, 4]. However, due to a large number of RIS
elements, CSI acquisition is challenging for the RIS assisted system [5].

There are two typical categories of methods for CSI acquisition, which are
respectively the explicit CSI acquisition (i.e., channel estimation) and the
implicit CSI acquisition (i.e., beam training). For the first category, the BS
sends the pilot signals to the user through the RIS, and the user directly
estimates the channel based on the received pilot signals [6]. Since the RIS
element is usually passive, only the cascaded channel, i.e., the cascade of
the channel from the BS to the RIS and the channel from the RIS to the user,
can be estimated by least squares (LS) [7] or minimum mean square error (MMSE)
algorithm [8]. The high-dimensional cascaded channel estimation will lead to
unaffordable pilot overhead in the RIS assisted system. In order to solve this
problem, two types of low-overhead cascaded channel estimation schemes have
been proposed [6]. On the one hand, some compressive sensing (CS) algorithms
can be used to estimate the high-dimensional cascaded channel by leveraging
the sparsity of the angular cascaded channel [9, 10]. On the other hand, the
multi-user correlation is exploited to reduce the pilot overhead by
considering that all users communicate with the BS via the same RIS [11].
However, for this category of method, since RIS cannot preform the reliable
reflecting beamforming before channel estimation, the received signal-to-noise
ratio (SNR) is usually low. It is difficult for channel estimation to achieve
the satisfactory channel estimation accuracy with the low received SNR.

The second category is beam training, where CSI can be obtained by estimating
the physical directions of channel paths instead the entire channel. This beam
training method has been widely considered in the existing 5G system,
especially for millimeter-wave frequency [12, 13]. Specifically, the BS and
the user preform the training procedure through multiple directional beams
(codewords) predefined in the codebook to search the optimal directional beam.
After beam training, the physical directions of channel paths can be
effectively obtained [14]. Compared with channel estimation, beam training can
directly achieve the reliable beamforming by the training procedure, which can
avoid estimating the entire channel with the low received SNR. Recently, the
beam training method has been extended to the RIS assisted system for CSI
acquisition [15, 16, 17]. The basic idea is that based on the cascaded array
steering vector of the RIS cascaded channel, the codebook consisting of
multiple RIS directional beams is firstly designed, and then the training
procedure between the RIS and the user is performed to search the optimal RIS
directional beam [15]. By considering that the cascaded array steering vector
is mainly determined by the angle differences at the RIS, the partial search
based beam training scheme was further proposed to reduce the search
complexity [16].

However, the existing codebook and beam training schemes may not be applicable
any more with the increasing number of RIS elements. Specifically, the RIS
assisted system is faced with the “multiplicative fading” effect [18, 19, 20],
where the equivalent path loss of the BS-RIS-user reflecting link is the
product of (instead of the sum of) the path losses of the BS-RIS link and RIS-
user link. Thanks to low cost and low power consumption, more and more RIS
elements are expected to deploy to compensate for the severe path loss [19].
RIS is more likely to develop into extremely large-scale RIS (XL-RIS) for
future 6G communications, which will lead to the fundamental transformation of
electromagnetic radiation field structure [21]. The electromagnetic radiation
field can be divided into far-field region and near-field region [22], which
are corresponding to the far-field channel model and near-field channel model,
respectively. The boundary of these two fields is determined by the Rayleigh
distance [22], which is proportional to the square of the array aperture. In
the RIS assisted system, the array aperture is not very large, and the
Rayleigh distance is small. The scatters are generally assumed in the far-
field region of RIS. The existing codebook for beam training is designed based
on the far-field channel model [15, 16, 17]. With the increasing number of RIS
elements from RIS to XL-RIS (e.g., from 256 to 1024), the array aperture of
XL-RIS is very large, and the Rayleigh distance increases accordingly [21].
The scatters are more likely to be in the near-field region of XL-RIS, and the
near-field channel model should be considered in the XL-RIS assisted system.
The existing far-field codebook mismatches the near-field channel model. Thus,
the corresponding far-field beam training will cause severe performance loss
in the XL-RIS assisted near-field communications. Unfortunately, this
important problem has not been studied in the literature.

To full in this gap, we propose the efficient near-field beam training schemes
by designing the near-field codebook to match the near-field channel model in
this paper111Simulation codes will be provided in the following link to
reproduce the results presented in this paper after publication:
http://oa.ee.tsinghua.edu.cn/dailinglong/publications/publications.html.. Our
contributions are summarized as follows.

  1. 1.

We design the near-field codebook to match the near-field channel model, and
then propose the corresponding near-field beam training scheme for XL-RIS.
Specifically, by considering the near-field cascaded array steering vector of
the XL-RIS cascaded channel, the near-field codebook is firstly designed,
where each codeword is determined by a pair of sampled points in the
$x\mbox{-}y\mbox{-}z$ coordinate system. Then, the optimal codeword for XL-RIS
is obtained by the exhausted training procedure between the XL-RIS and the
user.

  2. 2.

In order to reduce the beam training overhead, we further design a
hierarchical near-field codebook and propose the corresponding hierarchical
near-field beam training scheme for XL-RIS. Compared with the near-field
codebook, the hierarchical near-field codebook consists of several different
levels of sub-codebooks, which are determined by different sampling ranges and
sampling steps. During beam training, we search from the first level sub-
codebook to the last level sub-codebook in turn, where the sampling ranges and
sampling steps gradually become smaller. Finally, the globally optimal
codeword can be obtained in the last level sub-codebook associated with the
minimum sampling ranges and sampling steps.

The rest of the paper is organized as follows. In Section II, we firstly
introduce the signal model, and then review the existing far-field channel
model and far-field codebook. The near-field channel model for the XL-RIS
assisted system is also presented in Section II. In Section III, the near-
field codebook is designed and the corresponding near-field beam training
scheme is proposed, and then the hierarchical near-field codebook based beam
training is further proposed to reduce the beam training overhead. Simulation
results and conclusions are provided in Section IV and Section V,
respectively.

Notation: Lower-case and upper-case boldface letters ${\bf{a}}$ and ${\bf{A}}$
denote a vector and a matrix, respectively; ${{{\bf{a}}^{*}}}$ and
${{{\bf{a}}^{H}}}$ denote the conjugate and conjugate transpose of vector
$\bf{a}$, respectively; ${{\|{\bf{a}}\|_{2}}}$ denotes the $l_{2}$ norm of
vector $\bf{a}$; ${{{\bf{A}}^{H}}}$ denotes the conjugate transpose of matrix
$\bf{A}$. $\cal CN\left(\mu,\sigma\right)$ denotes the probability density
function of the circularly symmetric complex Gaussian distribution with mean
$\mu$ and variance $\sigma^{2}$. Finally, ${\rm{diag}}\left({\bf{a}}\right)$
denotes the diagonal matrix with the vector $\bf{a}$ on its diagonal.

##  II System Model

In this section, we will first introduce the signal model of the XL-RIS
assisted communication system. Then, the existing far-field channel model and
the far-field codebook for beam training will be briefly reviewed. Finally,
the near-field channel model for XL-RIS is presented.

###  II-A Signal Model

Figure 1: The XL-RIS assisted wireless communication system.

As shown in Fig. 1, a XL-RIS is deployed between the BS with $M$-element
antenna array and a single-antenna user to provide a reflecting link to assist
communication, where the direct link between the BS and the user is blocked by
obstacles [23, 15]. The XL-RIS consisting of $N=N_{1}\times N_{2}$ elements is
placed in the $x\mbox{-}z$ plane, where the center of the XL-RIS is at the
origin of the $x\mbox{-}y\mbox{-}z$ coordinate system.

Let ${\bf{G}}\in\mathbb{C}^{N\times M}$ denote the channel from the BS to the
XL-RIS and ${\bf{h}}_{r}\in\mathbb{C}^{1\times N}$ denote the channel from the
XL-RIS to the user. By considering the downlink transmission, the received
signal $r$ at the user can be expressed by

$r={\bf{h}}_{r}{\rm{diag}}\left({\bm{\theta}}\right){\bf{Gv}}s+n,$ (1)

where ${\bm{\theta}}=[\theta_{1},\cdots,\theta_{N}]\in\mathbb{C}^{N\times 1}$
is the reflecting beamforming vector at the XL-RIS with $\theta_{n}$
representing the reflecting coefficient at the $n$th RIS element
$(n=1,\cdots,N)$, ${\bf{v}}\in\mathbb{C}^{M\times 1}$ represents the
beamforming vector at the BS, $s$ represents the symbol transmitted by the BS,
$n\sim{\cal C}{\cal N}\left({0,\sigma^{2}}\right)$ represents the received
noise at the user with ${\sigma^{2}}$ representing the noise power.

To design the effective beamforming vectors ${\bf{v}}$ and ${\bm{\theta}}$, it
is necessary to acquire the accurate CSI [3, 4]. Since there are extremely
large number of RIS elements, channel estimation cannot achieve the
satisfactory channel estimation with low pilot overhead. By contrast, beam
training is a more effective way to acquire CSI [15, 17]. Specifically, since
the XL-RIS is generally dominated by the main path (or a few paths), we only
need to search the physical direction of the main path by beam training
instead of explicitly estimating the entire channel. Thus, in the following
description, only the main path is concerned, and the corresponding beam
training method will be investigated to search the optimal directional beam to
align with the main path.

Moreover, since the BS and the XL-RIS are generally deployed at fixed
positions, the channel ${\bf{G}}$ from the BS to the XL-RIS has a much longer
channel coherence time than the channel ${\bf{h}}_{r}$ from the XL-RIS to the
user due to the user’s mobility [15]. For simplicity, we assume that the
beamforming vector ${\bf{v}}$ at the BS has been aligned with the main path of
the channel $\bf{G}$ [15]. In this paper, we only focus on the beam training
at the XL-RIS. Next, we will briefly review the existing far-field channel
model and the corresponding far-field codebook for beam training.

###  II-B Far-Field Channel Model and Far-Filed Codebook

Based on the far-field channel model, $\bf{G}$ and ${\bf{h}}_{r}$ can be
respectively represented by

${\bf{G}}_{\rm{far\mbox{-}field}}={\alpha_{G}}{\bf{a}}\left({\phi}_{G_{r}},{\psi}_{G_{r}}\right){\bf{b}}^{T}\left({\phi}_{G_{t}},{\psi}_{G_{t}}\right),$
(2)
${\bf{h}}^{r}_{\rm{far\mbox{-}field}}={\alpha_{r}}{\bf{a}}^{T}\left({\phi}_{r},{\psi}_{r}\right),$
(3)

where ${\alpha_{G}}$ and ${\alpha_{r}}$ represent the path gains,
${\phi}_{G_{r}}$ and ${\psi}_{G_{r}}$ represent the spatial angles at the XL-
RIS for the channel $\bf{G}$, ${\phi}_{G_{t}}$ and ${\psi}_{G_{t}}$ represent
the spatial angles at the BS for the channel $\bf{G}$, ${\phi}_{r}$ and
${\psi}_{r}$ represent the spatial angles at the XL-RIS for the channel
${\bf{h}}_{r}$. ${\bf{a}}(\phi,\psi)$ and ${\bf{b}}(\phi,\psi)$ represent the
far-field array steering vector associated to the XL-RIS and the BS,
respectively. Take ${\bf{a}}(\phi,\psi)$ as an example, it can be expressed as
[10]

${\bf{a}}\left(\phi,\psi\right)={\left[{{e^{-j2{\pi}{\phi}{\bf{n}}_{1}}}}\right]}{\otimes}{\left[{{e^{-j2{\pi}{\psi}{\bf{n}}_{2}}}}\right]},$
(4)

where ${\bf{n}}_{1}=[0,1,\cdots,N_{1}-1]^{T}$ and
${\bf{n}}_{2}=[0,1,\cdots,N_{2}-1]^{T}$.
$\phi=d_{f}{\rm{sin}}\left(\vartheta\right){\rm{cos}}\left(\upsilon\right)/{\lambda}$
and $\psi=d_{f}{\rm{sin}}\left(\upsilon\right)/{\lambda}$, where $\vartheta$
and $\upsilon$ respectively represent the physical angles in the azimuth and
elevation, $\lambda$ is the carrier wavelength, and $d_{f}$ is the element
spacing satisfying $d_{f}=\lambda/2$.

By considering that the beamforming vector $\bf{v}$ at the BS has been
designed, i.e., ${\bf{v}}=\frac{{\bf{b}}^{*}}{\sqrt{M}}$, the receiver signal
$r$ in (1) can be further represented by

$\displaystyle r=$
$\displaystyle{\alpha}{\bf{a}}^{T}\left({\phi}_{r},{\psi}_{r}\right){\rm{diag}}\left({\bm{\theta}}\right){\bf{a}}\left({\phi}_{G_{r}},{\psi}_{G_{r}}\right){\bar{s}}+n$
(5) $\displaystyle=$
$\displaystyle{\alpha}{\bm{\theta}}^{T}{\rm{diag}}\left({\bf{a}}\left({\phi}_{r},{\psi}_{r}\right)\right){\bf{a}}\left({\phi}_{G_{r}},{\psi}_{G_{r}}\right){\bar{s}}+n$
$\displaystyle=$
$\displaystyle{\alpha}{\bm{\theta}}^{T}{\bf{a}}\left({\phi}_{G_{r}}+{\phi}_{r},{\psi}_{G_{r}}+{\psi}_{r}\right){\bar{s}}+n$
$\displaystyle=$
$\displaystyle{\bm{\theta}}^{T}{\bar{{\bf{h}}}}_{\rm{far\mbox{-}field}}{\bar{s}}+n,$

where
${\bar{{\bf{h}}}}_{\rm{far\mbox{-}field}}={\alpha}{\bf{a}}\left({\phi}_{G_{r}}+{\phi}_{r},{\psi}_{G_{r}}+{\psi}_{r}\right)$
denotes the far-field cascaded channel, $\alpha={\alpha}_{G}{\alpha}_{r}$
denotes the effective gain of ${\bar{{\bf{h}}}}_{\rm{far\mbox{-}field}}$, and
$\bar{s}={\bf{b}}^{T}\left({\phi}_{G_{t}},{\psi}_{G_{t}}\right){\bf{v}}s$
denotes the effective transmitted symbol.

For beam training, the entire procedure can be divided into multiple time
slots. In different time slots, the reflecting beamforming vector
${\bm{\theta}}$ is set as different codewords in the predefined codebook,
which will equivalently produce different directional beams. For each
codeword, the user will measure the strength of the received signal $r$ and
feedback the optimal codeword index. Based on the far-field array steering
vector in (4), the existing far-field codebook ${\bf{F}}$ is generally
designed as [15]

${\bf{F}}=\left[{\bf{a}}^{*}\left({\phi}_{1},{\psi}_{1}\right),\cdots,{\bf{a}}^{*}\left({\phi}_{1},{\psi}_{N_{1}}\right),\cdots,{\bf{a}}^{*}\left({\phi}_{N_{1}},{\psi}_{1}\right),\cdots,{\bf{a}}^{*}\left({\phi}_{N_{1}},{\psi}_{N_{2}}\right)\right],$
(6)

where ${\phi}_{n}={\frac{2n-N_{1}-1}{N_{1}}}$ with $n=1,2,\cdots,N_{1}$ and
${\psi}_{n}={\frac{2n-N_{2}-1}{N_{2}}}$ for ${n=1,2,\cdots,N_{2}}$. Each
column of $\bf{F}$ represents a codeword for ${\bm{\theta}}$.

The existing beam training schemes are mainly based on the above far-field
codebook [15, 16, 17]. However, when the RIS develops into XL-RIS, the far-
field codebook and beam training may not be applicable any more, which will be
explained in detail in the next Section II-C.

###  II-C Near-Field Channel Model

Figure 2: The near-field region and the far-field region [21].

Specifically, as shown in Fig. 2, the electromagnetic radiation field in
wireless communications can be divided into far-field region and near-field
region [22], where different fields will result in different channel models.
The bound between these two fields is determined by the Rayleigh distance
$Z=\frac{2D^{2}}{\lambda}$, where $D$ represents the array aperture. In the
conventional RIS assisted system, since the array aperture of the RIS is not
too large, the corresponding Rayleigh distance is small. The scatters are in
the far-field region of RIS [3, 23, 15], where the RIS channel can be modeled
under the planar wave assumption, as described in (2) and (3). With the
increase of the array aperture in the XL-RIS assisted system, the
corresponding Rayleigh distance also increases. For example, we consider that
the carrier frequency is $30$ GHz and the corresponding carrier wavelength is
$\lambda=0.01$ meters. When the array aperture for RIS is $D=0.1$ meters, the
Rayleigh distance is only $Z=2$ meters. When the array aperture for XL-RIS
increases to $D=1$ meter, the Rayleigh distance can reach $Z=200$ meters.
Thus, in the XL-RIS assisted system, the scatters are more likely to be in the
near-field region, where the XL-RIS channel should be modeled under the
spherical wave assumption. Next, we will introduce the near-field channel
model of XL-RIS.

For convenience of description, the distances and coordinates are normalized
by the carrier wavelength $\lambda$ in the following of this paper [24]. The
vertical or horizontal distance between two adjacent RIS elements is set to
$d$. The coordinate of the RIS element can be represented as
$((n_{1}-\frac{N_{1}+1}{2})d,0,(n_{2}-\frac{N_{2}+1}{2})d)$ in the
$x\mbox{-}y\mbox{-}z$ coordinate system, where $n_{1}=1,\cdots,N_{1}$ and
$n_{2}=1,\cdots,N_{2}$.

The near-field channel ${\bf{h}}^{r}_{\rm{near\mbox{-}field}}$ from the XL-RIS
to the user can be represented by [24]

${\bf{h}}^{r}_{\rm{near\mbox{-}field}}={\alpha_{r}}{\bf{c}}^{T}\left(x_{r},y_{r},z_{r}\right),$
(7)

where $(x_{r},y_{r},z_{r})$ represents the coordinate of the scatter
corresponding to the main path between the XL-RIS and user. Compared with the
far-field channel model in (3), the array steering vector
${\bf{c}}\left(x_{r},y_{r},z_{r}\right)$ for the near-field channel model is
derived based on the the spherical wave assumption, which can represented by
[24]

${\bf{c}}(x_{r},y_{r},z_{r})=\left[e^{-j2\pi D^{r}(1,1)},\cdots,e^{-j2\pi
D^{r}(1,N_{2})},\cdots,e^{-j2\pi D^{r}(N_{1},1)},\cdots,e^{-j2\pi
D^{r}(N_{1},N_{2})}\right]^{T},$ (8)

where
$D^{r}(n_{1},n_{2})=\sqrt{(x_{r}-(n_{1}-\frac{N_{1}+1}{2})d)^{2}+y_{r}^{2}+(z_{r}-(n_{2}-\frac{N_{2}+1}{2})d)^{2}}$
represents the distance from the $(n_{1},n_{2})$-th RIS element to
$(x_{r},y_{r},z_{r})$.

Similarly, the array steering vector at the RIS of the channel $\bf{G}$ from
the BS to the XL-RIS should be also near-field. Thus, the near-field cascaded
channel ${\bar{{\bf{h}}}}_{\rm{near\mbox{-}field}}$ in (5) can be represented
by

${\bar{{\bf{h}}}}_{\rm{near\mbox{-}field}}={\alpha}{{\bar{\bf{c}}}}\left((x_{G_{r}},y_{G_{r}},z_{G_{r}}),(x_{r},y_{r},z_{r})\right),$
(9)

where $(x_{G_{r}},y_{G_{r}},z_{G_{r}})$ represents the coordinate of the
scatter corresponding to the main path between the BS and XL-RIS. The near-
field cascaded array steering vector
${{\bar{\bf{c}}}}\left((x_{G_{r}},y_{G_{r}},z_{G_{r}}),(x_{r},y_{r},z_{r})\right)$
can be represented by

$\displaystyle{{\bar{\bf{c}}}}\left((x_{G_{r}},y_{G_{r}},z_{G_{r}}),(x_{r},y_{r},z_{r})\right)=\left[e^{-j2\pi
D(1,1)},\cdots,e^{-j2\pi D(1,N_{2})},\cdots,\right.$ (10)
$\displaystyle\left.e^{-j2\pi D(N_{1},1)},\cdots,e^{-j2\pi
D(N_{1},N_{2})}\right]^{T},$

where $D(n_{1},n_{2})=D^{r}(n_{1},n_{2})+D^{G_{r}}(n_{1},n_{2})$ represents
the effective distance of ${\bar{{\bf{h}}}}_{\rm{near\mbox{-}field}}$, and
$D^{G_{r}}(n_{1},n_{2})=\sqrt{(x_{G_{r}}-(n_{1}-\frac{N_{1}+1}{2})d)^{2}+y_{G_{r}}^{2}+(z_{G_{r}}-(n_{2}-\frac{N_{2}+1}{2})d)^{2}}$.
$\left(x_{G_{r}},y_{G_{r}},z_{G_{r}}\right)$ satisfies
$X_{\rm{min}}^{G_{r}}\leq x_{G_{r}}\leq X_{\rm{max}}^{G_{r}}$,
$Y_{\rm{min}}^{G_{r}}\leq y_{G_{r}}\leq Y_{\rm{max}}^{G_{r}}$,
$Z_{\rm{min}}^{G_{r}}\leq z_{G_{r}}\leq Z_{\rm{max}}^{G_{r}}$, and
$\left(x_{r},y_{r},z_{r}\right)$ satisfies $X_{\rm{min}}^{r}\leq x_{r}\leq
X_{\rm{max}}^{r}$,$Y_{\rm{min}}^{r}\leq y_{r}\leq Y_{\rm{max}}^{r}$, and
$Z_{\rm{min}}^{r}\leq z_{r}\leq Z_{\rm{max}}^{r}$.

Compared with the far-field cascaded array steering vector only associated
with the angles in (4), the near-field cascaded array steering vector is
determined by a pair of points in the $x\mbox{-}y\mbox{-}z$ coordinate system,
i.e., $(x_{G_{r}},y_{G_{r}},z_{G_{r}})$ and $(x_{r},y_{r},z_{r})$. The
existing far-field codebook mismatches the near-field channel model. Thus, the
corresponding far-field beam training will cause severe performance loss in
the XL-RIS assisted near-field communications. In this paper, we design the
near-field codebook to match the near-field channel model, and then propose
the corresponding near-field beam training for XL-RIS, which will be
introduced in the next Section III.

##  III Proposed Near-Field Codebook Design and Beam Training Scheme for XL-
RIS

In this section, we will introduce the proposed near-field codebook and the
corresponding near-field beam training. Then, a hierachical near-field
codebook and the corresponding beam training will be further proposed to
reduce the beam training overhead.

###  III-A Proposed Near-Field Codebook Design and Beam training

Inspired by the near-field dictionary matrix design for the XL-MIMO channel
estimation [24], we design a near-field codebook for the XL-RIS beam training.
In the near-field dictionary matrix proposed in [24] for the extremely large-
scale linear antenna array, the considered entire two-dimensional (2D) plane
is divided by several sampled points in the $x\mbox{-}y$ coordinate system.
Each column of the dictionary matrix is the corresponding near-field array
steering vector for the linear array associated with one sampled point. If the
near-field codebook for the planar array is required to design in the XL-MIMO
system, we only need to extend the 2D plane to the three-dimensional (3D)
space, where each codeword can be generated based on the near-field array
steering vector for the planar array associated with one sampled point in the
$x\mbox{-}y\mbox{-}z$ coordinate system. However, the near-field cascaded
channel brings new challenges to the codebook design for XL-RIS .

Specifically, since the near-field cascaded array steering vector
${{\bar{\bf{c}}}}$ of the near-field cascaded channel
${\bar{{\bf{h}}}}_{\rm{near\mbox{-}field}}$ is determined by the sum of the
distance from $\left(x_{G_{r}},y_{G_{r}},z_{G_{r}}\right)$ to the XL-RIS and
the distance from $\left(x_{r},y_{r},z_{r}\right)$ to the XL-RIS, each
codeword for XL-RIS should be related to a pair of sampled points in the
$x\mbox{-}y\mbox{-}z$ coordinate system, instead of only one sampled point
[24]. Next, we will introduce the designed near-field codebook based on the
near-field cascaded array steering vector.

####  III-A1 Near-Field Codebook Design

Let $\Xi^{G_{r}}$ and $\Xi^{r}$ denote the two collections of sampled points
corresponding to $\left(x_{G_{r}},y_{G_{r}},z_{G_{r}}\right)$ and
$\left(x_{r},y_{r},z_{r}\right)$, which can be represented as

$\displaystyle{\Xi}^{G_{r}}=\left\\{(x^{G_{r}}_{s},y^{G_{r}}_{s},z^{G_{r}}_{s})|x^{G_{r}}_{s}=X^{G_{r}}_{\rm{min}},X^{G_{r}}_{\rm{min}}+\Delta
x^{G_{r}},\cdots,X^{G_{r}}_{\rm{max}};y^{G_{r}}_{s}=Y^{G_{r}}_{\rm{min}},\right.$
(11) $\displaystyle\left.Y^{G_{r}}_{\rm{min}}+\Delta
y^{G_{r}},\cdots,Y^{G_{r}}_{\rm{max}};z^{G_{r}}_{s}=Z^{G_{r}}_{\rm{min}},Z^{G_{r}}_{\rm{min}}+\Delta
z^{G_{r}},\cdots,Z^{G_{r}}_{\rm{max}}\right\\},$
$\displaystyle{\Xi}^{r}=\left\\{(x^{r}_{s},y^{r}_{s},z^{r}_{s})|x^{r}_{s}=X^{r}_{\rm{min}},X^{r}_{\rm{min}}+\Delta
x^{r},\cdots,X^{r}_{\rm{max}};y^{r}_{s}=Y^{r}_{\rm{min}},\right.$ (12)
$\displaystyle\left.Y^{r}_{\rm{min}}+\Delta
y^{r},\cdots,Y^{r}_{\rm{max}};z^{r}_{s}=Z^{r}_{\rm{min}},Z^{r}_{\rm{min}}+\Delta
z^{r},\cdots,Z^{r}_{\rm{max}}\right\\},$

where $\Delta x^{G_{r}}$, $\Delta y^{G_{r}}$ and $\Delta z^{G_{r}}$ represent
the sampling step on the $x$-axis, $y$-axis and $z$-axis for ${\Xi}^{G_{r}}$,
respectively. $\Delta x^{r}$, $\Delta y^{r}$ and $\Delta z^{r}$ represent the
sampling step on the $x$-axis, $y$-axis and $z$-axis for ${\Xi}^{r}$,
respectively. Let $\Delta=[\Delta x^{G_{r}},\Delta y^{G_{r}},\Delta
z^{G_{r}},\Delta x^{r},\Delta y^{r},\Delta z^{r}]$ denote all sampling steps.
Given a pair of sampled points $(x^{G_{r}}_{s},y^{G_{r}}_{s},z^{G_{r}}_{s})$
and $(x^{r}_{s},y^{r}_{s},z^{r}_{s})$, the effective sampled distance
$D_{s}(n_{1},n_{2})$ can be presented by

$\displaystyle D_{s}(n_{1},n_{2})=$
$\displaystyle\sqrt{\bigg{(}x^{G_{r}}_{s}-(n_{1}-\frac{N_{1}+1}{2})d\bigg{)}^{2}+{y^{G_{r}}_{s}}^{2}+\bigg{(}z^{G_{r}}_{s}-(n_{2}-\frac{N_{2}+1}{2})d\bigg{)}^{2}}$
(13) $\displaystyle+$
$\displaystyle\sqrt{\bigg{(}x^{r}_{s}-(n_{1}-\frac{N_{1}+1}{2})d\bigg{)}^{2}+{y^{r}_{s}}^{2}+\bigg{(}z^{r}_{s}-(n_{2}-\frac{N_{2}+1}{2})d\bigg{)}^{2}},$

where $n_{1}=1,2,\cdots,N_{1}$ and $n_{2}=1,2,\cdots,N_{2}$.

Inputs: The two collections of sampled points $\Xi^{G_{r}}$ and $\Xi^{r}$, the
number of RIS elements $N_{1}$ and $N_{2}$.

Initialization: ${\bf{W}}=\emptyset$, $L=0$.

1\. for $(x^{G_{r}}_{s},y^{G_{r}}_{s},z^{G_{r}}_{s})\in\Xi^{G_{r}}$ do

2\. for $(x^{r}_{s},y^{r}_{s},z^{r}_{s})\in\Xi^{r}$ do

3\. ${\bar{\bf{c}}}_{s}=\left[e^{-j2\pi D_{s}(1,1)},\cdots,e^{-j2\pi
D_{s}(1,N_{2})},\cdots,e^{-j2\pi D_{s}(N_{1},1)},\cdots,e^{-j2\pi
D_{s}(N_{1},N_{2})}\right]^{H}$

4\. if ${\bf{w}}\notin{\bf{W}}$ then

5\. ${\bf{W}}=[{\bf{W}},{\bar{\bf{c}}}_{s}]$

6\. $L=L+1$

7\. end if

8\. end for

9\. end for

Output: The designed near-field XL-RIS codebook ${\bf{W}}$, and the codebook
size $L$.

Algorithm 1 Near-field codebook design

Algorithm 1 shows the specific near-field codebook design procedure. From Step
3, we can find that the near-field codeword is generated based on the near-
field cascaded array steering vector, which is related to a pair of sampled
points $(x^{G_{r}}_{s},y^{G_{r}}_{s},z^{G_{r}}_{s})$ and
$(x^{r}_{s},y^{r}_{s},z^{r}_{s})$. It is noted that different pairs of sampled
points may produce the same effective sampled distance, which will result in
the same codeword. In order to solve this problem, we need to ensure that each
new codeword is different from all previous codewords, as shown in Steps 4-7.
Finally, the designed near-field codebook ${\bf{W}}$ is obtained, where each
column represents one codeword for the reflecting beamforming vector
$\bm{\theta}$ at the XL-RIS. The corresponding codebook size $L$ is also
obtained.

After designing the near-field codebook for XL-RIS, the beam training
procedure between the XL-RIS and the user can be performed to search the
optimal codeword for the reflecting beamforming vector $\bm{\theta}$ at the
XL-RIS. Next, we will introduce the corresponding near-field beam training
scheme.

####  III-A2 Near-Field Beam Training

The specific near-field beam training procedure is summarized in Algorithm 2,
where all the codewords in the designed near-field codebook ${\bf{W}}$ need to
be traversed. The entire training procedure can be divided into $L$ time
slots. In $l$-th time slots, the BS transmits the effective symbol $\bar{s}$
to the user, where the reflecting beamforming vector ${\bm{\theta}}_{l}$ is
set as the $l$-th codeword in the designed near-field codebook ${\bf{W}}$ at
the XL-RIS, as shown in Step 3. After $L$ time slots, the user can obtain the
optimal codeword based on all received signals $\\{r_{l}\\}_{l=1}^{L}$ with
the help of Steps 4-7. Finally, the optimal codeword index $l_{\rm{opt}}$ is
fed back from the user to XL-RIS.

Inputs: The designed near-field XL-RIS codebook ${\bf{W}}$, and the effective
transmitted symbol $\bar{s}$.

Initialization: $l=0$, $|r|_{\rm{opt}}=0$, $l_{\rm{opt}}=0$.

1\. for ${{\bar{\bf{c}}}_{s}}\in{\bf{W}}^{H}$ do

2\. $l=l+1$

3\.
${r}_{l}={\bm{\theta}}_{l}^{T}{\bar{{\bf{h}}}}_{\rm{near\mbox{-}field}}{\bar{s}}+n_{l}$,
where ${\bm{\theta}}_{l}={{\bar{\bf{c}}}_{s}}$

4\. if $|r_{l}|>|r|_{\rm{opt}}$ then

5\. $l_{\rm{opt}}=l$

6\. $|r|_{\rm{opt}}=|r_{l}|$

7\. end if

8\. end for

Output: The feedback optimal codeword index $l_{\rm{opt}}$ from the user.

Algorithm 2 Near-field beam training

Since the near-field cascaded array steering vector for XL-RIS is jointly
determined by a pair of sampled points, the codebook size $L$ is usually
large. This exhausted training procedure will lead to huge beaming training
overhead. In order to reduce the beam training overhead, we further design a
hierachical near-field codebook and propose the corresponding hierachical beam
training scheme.

###  III-B Proposed Hierachical Near-Field Codebook Design and Beam training

To reduce the beam training overhead, one effective way is to reduce the
codebook size. By referring to (11) and (12), we can find the codebook size
for the entire sampling space is mainly determined by the sampling steps on
the $x$-axis, $y$-axis and $z$-axis. If the sampling steps are increased, the
codebook size will be reduced. But the performance of the beam training will
be also degraded accordingly, since it is difficult to accurately locate the
scatters corresponding to the main paths with the reduced codebook. In order
to solve this problem, we design a hierachical near-field codebook, which
consists of several different levels of sub-codebooks. These different levels
of sub-codebooks are determined by different sampling ranges and sampling
steps.

Specifically, let $K$ denote the number of different levels of sub-codebooks.
In the $k$-th sub-codebook ($k=1,2,\cdots,K$), the corresponding collections
of sampled points ${\Xi}^{G_{r}}_{k}$ and ${\Xi}^{r}_{k}$ can be defined as

$\displaystyle{\Xi}^{G_{r}}_{k}=\left\\{(x^{G_{r},k}_{s},y^{G_{r},k}_{s},z^{G_{r},k}_{s})|x^{G_{r},k}_{s}=X^{G_{r},k}_{\rm{min}},X^{G_{r},k}_{\rm{min}}+\Delta
x^{G_{r},k},\cdots,X^{G_{r},k}_{\rm{max}};y^{G_{r},k}_{s}=Y^{G_{r},k}_{\rm{min}},\right.$
(14) $\displaystyle\left.Y^{G_{r},k}_{\rm{min}}+\Delta
y^{G_{r},k},\cdots,Y^{G_{r},k}_{\rm{max}};z^{G_{r},k}_{s}=Z^{G_{r},k}_{\rm{min}},Z^{G_{r},k}_{\rm{min}}+\Delta
z^{G_{r},k},\cdots,Z^{G_{r},k}_{\rm{max}}\right\\},$
$\displaystyle{\Xi}^{r}_{k}=\left\\{(x^{r,k}_{s},y^{r,k}_{s},z^{r,k}_{s})|x^{r,k}_{s}=X^{r,k}_{\rm{min}},X^{r,k}_{\rm{min}}+\Delta
x^{r,k},\cdots,X^{r,k}_{\rm{max}};y^{r,k}_{s}=Y^{r,k}_{\rm{min}},\right.$ (15)
$\displaystyle\left.Y^{r,k}_{\rm{min}}+\Delta
y^{r,k},\cdots,Y^{r,k}_{\rm{max}};z^{r,k}_{s}=Z^{r,k}_{\rm{min}},Z^{r,k}_{\rm{min}}+\Delta
z^{r,k},\cdots,Z^{r,k}_{\rm{max}}\right\\}.$

Take the sampling on the $x$-axis for ${\Xi}^{G_{r}}_{k}$ as an example,
$[X^{G_{r},k}_{\rm{min}},X^{G_{r},k}_{\rm{max}}]$ and $\Delta x^{G_{r},k}$
represent the sampling range and sampling step, respectively. Further, let
$R^{k}=\big{\\{}[X^{G_{r},k}_{\rm{min}},X^{G_{r},k}_{\rm{max}}],[Y^{G_{r},k}_{\rm{min}},Y^{G_{r},k}_{\rm{max}}],\\\
{[Z^{G_{r},k}_{\rm{min}},Z^{G_{r},k}_{\rm{max}}]},[X^{r,k}_{\rm{min}},X^{r,k}_{\rm{max}}],[Y^{r,k}_{\rm{min}},Y^{r,k}_{\rm{max}}],{[Z^{r,k}_{\rm{min}},Z^{r,k}_{\rm{max}}]}\big{\\}}$
and ${\Delta}^{k}=\\{\Delta x^{G_{r},k},\Delta y^{G_{r},k},\Delta
z^{G_{r},k},\\\ \Delta x^{r,k},\Delta y^{r,k},\Delta z^{r,k}\\}$ respectively
denote all sampling ranges and all sampling steps for the $k$-th level sub-
codebook. In this way, ${\Xi}^{G_{r}}_{k}$ and ${\Xi}^{r}_{k}$ can be
completely determined by $R^{k}$ and ${\Delta}^{k}$. Given ${\Xi}^{G_{r}}_{k}$
and ${\Xi}^{r}_{k}$, the $k$-th level sub-codebook ${\bf{W}}_{k}$ and the
corresponding codebook size $L_{k}$ can be further obtained by referring to
Algorithm 1. Fig. 3 shows the comparison between the near-field codebook and
the hierachical near-field codebook. In the hierachical near-field codebook,
from the $1$-st level sub-codebook to the $K$-th level sub-codebook, both the
corresponding sampling ranges and sampling steps gradually become smaller.
Thus, the codebook size of each level of sub-codeboook is not large.

Figure 3: Comparison between the near-field codebook and the hierachical near-
field codebook.

Based on the hierachical near-field codebook, we further propose the
hierachical near-field beam training scheme. The basic idea is to search from
the $1$-st level sub-codebook to the $K$-th level sub-codebook in turn, where
the sampling ranges of the latter level sub-codebook is determined by the
optimal codeword searched and the sampling steps by the former level sub-
codebook, as shown in Fig. 3. By assuming that the searched optimal codeword
for the $k$-th level sub-codebook is ${{\bar{\bf{c}}}_{s,k,\rm{opt}}}$ with
the corresponding sampled points
$(x^{G_{r}}_{s,k,\rm{opt}},y^{G_{r}}_{s,k,\rm{opt}},z^{G_{r}}_{s,k,\rm{opt}})$
and $(x^{r}_{s,k,\rm{opt}},y^{r}_{s,k,\rm{opt}},z^{r}_{s,k,\rm{opt}})$, the
sampling ranges of the $(k+1)$-th level sub-codebook can be determined
accordingly. Take $[X^{G_{r},k+1}_{\rm{min}},X^{G_{r},k+1}_{\rm{max}}]$ as an
example, it can be represented by

$[X^{G_{r},k+1}_{\rm{min}},X^{G_{r},k+1}_{\rm{max}}]=[x^{G_{r}}_{s,k,\rm{opt}}-\Delta
x^{G_{r},k}/2,x^{G_{r}}_{s,k,\rm{opt}}+\Delta x^{G_{r},k}/2].$ (16)

For the $1$-st level sub-codebook, the corresponding sampling ranges can be
set as
$R^{1}=\big{\\{}[X^{G_{r}}_{\rm{min}},X^{G_{r}}_{\rm{max}}],[Y^{G_{r}}_{\rm{min}},Y^{G_{r}}_{\rm{max}}],{[Z^{G_{r}}_{\rm{min}},Z^{G_{r}}_{\rm{max}}]},[X^{r}_{\rm{min}},X^{r}_{\rm{max}}],[Y^{r}_{\rm{min}},Y^{r}_{\rm{max}}],[Z^{r,k}_{\rm{min}},Z^{r,k}_{\rm{max}}]\big{\\}}$.
The initial sampling steps $\Delta^{1}$ should be set as bigger values to
reduce the codebook size. In this paper, we set $\Delta^{1}=A\Delta$, where
$\Delta$ is the sampling steps for the designed near-field codebook in Section
III-A, and $A$ is a scalar greater than $1$. Moreover, we define a step
control parameter $\delta$ ($0<\delta<1$) to gradually decrease the sampling
steps of the sub-codebooks.

Inputs: The number of different levels of sub-codebooks $K$, the initial
sampling ranges $R^{1}$, the initial sampling steps $\Delta^{1}$, the step
control parameter $\delta$, and the effective transmitted symbol $\bar{s}$,
the number of RIS elements $N_{1}$ and $N_{2}$.

Initialization: $l_{k}=0$, $|r|_{k,\rm{opt}}=0$ and $l_{k,\rm{opt}}=0$ for
$\forall k$

1\. for $k=1,2,\cdots,K$ do

2\. generate ${\Xi}^{G_{r}}_{k}$ and ${\Xi}^{r}_{k}$ based on $R^{k}$ and
$\Delta^{k}$ by (14) and (15)

3\. generate ${\bf{W}}_{k}$ based on ${\Xi}^{G_{r}}_{k}$ and ${\Xi}^{r}_{k}$
by Algorithm 1

4\. for ${{\bar{\bf{c}}}_{s,k}}\in{\bf{W}}_{k}$ do

5\. $l_{k}=l_{k}+1$

6\.
${r}_{l,k}={\bm{\theta}}_{l,k}^{T}{\bar{{\bf{h}}}}_{\rm{near\mbox{-}field}}{\bar{s}}+n_{l,k}$,
where ${\bm{\theta}}_{l,k}={{\bar{\bf{c}}}_{s,k}}$

7\. if $|r_{l,k}|>|r|_{k,\rm{opt}}$ then

8\. $l_{k,{\rm{opt}}}=l_{k}$

9\. $|r|_{k,\rm{opt}}=|r_{l,k}|$

10\. end if

11\. end for

12\. generate $R^{k+1}$ based on $l_{k,\rm{opt}}$ by (16)

13\. $\Delta^{k+1}=\delta\Delta^{k}$

14.end for

Output: The feedback optimal codeword index $l_{K,{\rm{opt}}}$ from the user.

Algorithm 3 Hierachical near-field beam training

The specific hierachical near-field beam training procedure is summarized in
Algorithm 3, where the entire beam training procedure is divided into $K$
stages. In the $k$-th stage, the $k$-th level sub-codebook ${\bf{W}}_{k}$ is
firstly generated by Steps 2-3. Then, Steps 4-11 are performed to search the
optimal codeword in ${\bf{W}}_{k}$. It is noted that the searched optimal
codeword index $l_{k,\rm{opt}}$ should be fed back from the user to the XL-RIS
to generate the the sampling ranges $R^{k+1}$ and sampling steps
$\Delta^{k+1}$ for the $(k+1)$-th level sub-codebook, as shown in Steps 12-13.
Finally, the optimal codeword for the $K$-th level sub-codebook is regarded as
the searched globally optimal codeword in the hierachical near-field codebook.

From Algorithm 3, we can find that the corresponding beam training overhead is
$\sum_{k=1}^{K}L_{k}$. Since the sampling ranges and sampling steps for the
hierachical near-field codebook are carefully designed, $L_{k}$ for $\forall
k$ can be much less than $L$, which will be verified by the following
simulation results.

##  IV Simulation Results

In this section, we provide the simulation results to verify the performance
of the two proposed near-field beam training schemes.

For simulations, we consider that the number of antennas at the BS is $M=64$,
and the number of RIS elements at the XL-RIS is $N=512$ ($N_{1}=128$ and
$N_{2}=4$). The path gains are generated by ${\alpha_{G}\sim{\cal C}{\cal
N}\left({0,1}\right)}$ and ${\alpha_{r}\sim{\cal C}{\cal
N}\left({0,1}\right)}$. The vertical or horizontal distance between two
adjacent RIS elements is set as $d=1/2$ [24]. The distance from the XL-RIS to
the scatter is limited to $X^{G_{r}}_{\rm{min}}=X^{r}_{\rm{min}}=-1200d$,
$X^{G_{r}}_{\rm{max}}=X^{r}_{\rm{max}}=1200d$,
$Y^{G_{r}}_{\rm{min}}=Y^{r}_{\rm{min}}=10d$,
$Y^{G_{r}}_{\rm{max}}=Y^{r}_{\rm{max}}=200d$,
$Z^{G_{r}}_{\rm{min}}=Z^{r}_{\rm{min}}=-400d$,
$Z^{G_{r}}_{\rm{max}}=Z^{r}_{\rm{max}}=-400d$. The symbol transmitted by the
BS is set as $s=1$, and the beamforming vector at the BS is set as
${\bf{v}}=\frac{{\bf{b}}^{*}}{\sqrt{M}}$. Thus, the effective transmitted
symbol is $\bar{s}=1$. The SNR is defined as $1/{\sigma}^{2}$.

We compare the proposed near-field beam training scheme and the hierachical
near-field beam training scheme with the existing far-field beam training
scheme [15]. In the near-field beam training scheme, the sampling steps on all
$x$-axis, $y$-axis and $z$-axis are set to the same, i.e., $\Delta
x^{G_{r}}=\Delta y^{G_{r}}=\Delta z^{G_{r}}=\Delta x^{r}=\Delta y^{r}=\Delta
z^{r}=\Delta_{s}$. That is to say
$\Delta=[\Delta_{s},\Delta_{s},\Delta_{s},\Delta_{s},\Delta_{s},\Delta_{s}]$.
In the hierachical near-field beam training scheme, we set $A=4$, and the
initial sampling steps $\Delta^{1}=A\Delta$. The step control parameter is set
as $\delta=0.25$. The number of different levels of sub-codebooks is set as
$K=2$. In the far-field beam training scheme, the far-field codebook $\bf{F}$
defined in (3) is adopted. Moreover, we provide the beamforming scheme with
perfect CSI as the upper bound of performance, i.e.,
${\bm{\theta}}=\frac{{\bar{\bf{c}}}^{*}}{\sqrt{N}}$.

Figure 4: Achievable rate performance comparison against the SNR. Figure 5:
Beam training overhead comparison against the sampling step $\Delta_{s}$.

Fig. 4 shows the achievable rate performance comparison against the SNR, where
$\Delta_{s}=100d$. We can find that compared with the existing far-field beam
training scheme, the two proposed near-field beam training schemes can achieve
better achievable rate performance. Due to the error propagation among
different levels of sub-codebooks search, the performance of the hierachical
near-field beam training scheme is sightly worse than that of the near-field
beam training scheme. Specifically, the hierachical near-field beam training
scheme can achieve about $92\%$ achievable rate performance of the near-field
beam training scheme.

Fig. 5 further shows the beam training overhead comparison of the two proposed
near-field beam training schemes against the sampling step $\Delta_{s}$. We
can find that the hierachical near-field beam training scheme can greatly
reduce the beam training overhead. When $\Delta_{s}=100d$, the beam training
overhead of the near-field beam training scheme and the hierachical near-field
beam training scheme are respectively $147628$ and $15927$, where the latter
is only about $10\%$ of the former.

##  V Conclusions

In this paper, we have proposed the two near-field beam training schemes by
designing the near-field codebook for the XL-RIS assisted system. Simulation
results shows that the two proposed near-field beam training schemes can
achieve better performance than the existing far-field beam training scheme.
Particulary, compared with the near-field beam training scheme, the
hierachical near-field beam training scheme can reduce the beam training
overhead by about $90\%$ with about $92\%$ achievable rate performance. For
future works, the multi-beam training method can be used to the near-field XL-
RIS beam training to further reduce the beam training overhead.

## References

  * [1] E. Basar, M. Di Renzo, J. De Rosny, M. Debbah, M. Alouini, and R. Zhang, “Wireless communications through reconfigurable intelligent surfaces,” _IEEE Access_ , vol. 7, pp. 116 753–116 773, Aug. 2019.
  * [2] Q. Wu and R. Zhang, “Intelligent reflecting surface enhanced wireless network via joint active and passive beamforming,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 11, pp. 5394–5409, Nov. 2019.
  * [3] P. Wang, J. Fang, X. Yuan, Z. Chen, and H. Li, “Intelligent reflecting surface-assisted millimeter wave communications: Joint active and passive precoding design,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 12, pp. 14 960–14 973, Dec. 2020.
  * [4] Z. Zhang and L. Dai, “A joint precoding framework for wideband reconfigurable intelligent surface-aided cell-free network,” _IEEE Trans. Signal Process._ , vol. 69, pp. 4085–4101, Aug. 2021.
  * [5] Q. Wu, S. Zhang, B. Zheng, C. You, and R. Zhang, “Intelligent reflecting surface-aided wireless communications: A tutorial,” _IEEE Trans. Commun._ , vol. 69, no. 5, pp. 3313–3351, May 2021.
  * [6] X. Wei, D. Shen, and L. Dai, “Channel estimation for RIS assisted wireless communications: Part I - fundamentals, solutions, and future opportunities,” _IEEE Commun. Lett._ , vol. 25, no. 5, pp. 1398–1402, May 2021.
  * [7] D. Mishra and H. Johansson, “Channel estimation and low-complexity beamforming design for passive intelligent surface assisted MISO wireless energy transfer,” in _Proc. IEEE Int. Conf. Acoust., Speech Signal Process. (IEEE ICASSP’19)_ , Brighton, UK, May 2019, pp. 4659–4663.
  * [8] Q. Nadeem, H. Alwazani, A. Kammoun, A. Chaaban, M. Debbah, and M. S. Alouini, “Intelligent reflecting surface-assisted multi-user MISO communication: Channel estimation and beamforming design,” _IEEE Open J. Commun. Soc._ , vol. 1, pp. 661–680, May 2020.
  * [9] P. Wang, J. Fang, H. Duan, and H. Li, “Compressed channel estimation for intelligent reflecting surface-assisted millimeter wave systems,” _IEEE Signal Process. Lett._ , vol. 27, pp. 905–909, May 2020.
  * [10] X. Wei, D. Shen, and L. Dai, “Channel estimation for RIS assisted wireless communications: Part II - an improved method based on double-structured sparsity,” _IEEE Commun. Lett._ , vol. 25, no. 5, pp. 1402–1407, May 2021.
  * [11] Z. Wang, L. Liu, and S. Cui, “Channel estimation for intelligent reflecting surface assisted multiuser communications,” in _Proc. IEEE Wireless Commun. and Networking Conf. (IEEE WCNC’20)_ , Seoul, Korea, May 2020, pp. 1–6.
  * [12] W. Wu, D. Liu, X. Hou, and M. Liu, “Low-complexity beam training for 5G millimeter-wave massive MIMO systems,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 1, pp. 361–376, Jan. 2020.
  * [13] Z. Xiao, T. He, P. Xia, and X.-G. Xia, “Hierarchical codebook design for beamforming training in millimeter-wave communication,” _IEEE Trans. Wireless Commun._ , vol. 15, no. 5, pp. 3380–3392, May 2016.
  * [14] X. Gao, L. Dai, Z. Chen, Z. Wang, and Z. Zhang, “Near-optimal beam selection for beamspace mmWave massive MIMO systems,” _IEEE Commun. Lett._ , vol. 20, no. 5, pp. 1054–1057, May 2016.
  * [15] C. You, B. Zheng, and R. Zhang, “Fast beam training for IRS-assisted multiuser communications,” _IEEE Wireless Commun, Lett._ , vol. 9, no. 11, pp. 1845–1849, Nov. 2020.
  * [16] B. Ning, Z. Chen, W. Chen, Y. Du, and J. Fang, “Terahertz multi-user massive MIMO with intelligent reflecting surface: Beam training and hybrid beamforming,” _IEEE Trans. Veh. Technol._ , vol. 70, no. 2, pp. 1376–1393, Feb. 2021.
  * [17] J. Zhang, Y. Huang, J. Wang, X. You, and C. Masouros, “Intelligent interactive beam training for millimeter wave communications,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 3, pp. 2034–2048, Mar. 2021.
  * [18] M. Najafi, V. Jamali, R. Schober, and H. V. Poor, “Physics-based modeling and scalable optimization of large intelligent reflecting surfaces,” _IEEE Trans. Commun._ , vol. 69, no. 4, pp. 2673–2691, Apr. 2021.
  * [19] W. Tang, M. Z. Chen, X. Chen, J. Y. Dai, Y. Han, M. Di Renzo, Y. Zeng, S. Jin, Q. Cheng, and T. J. Cui, “Wireless communications with reconfigurable intelligent surface: Path loss modeling and experimental measurement,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 1, pp. 421–439, Jan. 2021.
  * [20] M. Di Renzo, A. Zappone, M. Debbah, M.-S. Alouini, C. Yuen, J. de Rosny, and S. Tretyakov, “Smart radio environments empowered by reconfigurable intelligent surfaces: How it works, state of research, and the road ahead,” _IEEE J. Sel. Areas Commun._ , vol. 38, no. 11, pp. 2450–2525, Nov. 2020\.
  * [21] M. Cui and L. Dai, “Channel estimation for extremely large-scale MIMO: Far-field or near-field?” _arXiv preprint arXiv:2108.07581_ , Aug. 2021.
  * [22] K. T. Selvan and R. Janaswamy, “Fraunhofer and fresnel distances: Unified derivation for aperture antennas.” _IEEE Ant. Propag. Mag._ , vol. 59, no. 4, pp. 12–15, Aug. 2017.
  * [23] L. Wei, C. Huang, G. C. Alexandropoulos, C. Yuen, Z. Zhang, and M. Debbah, “Channel estimation for RIS-empowered multi-user MISO wireless communications,” _IEEE Trans. Commun._ , vol. 69, no. 6, pp. 4144–4157, Jun. 2021.
  * [24] Y. Han, S. Jin, C. Wen, and X. Ma, “Channel estimation for extremely large-scale massive MIMO systems,” _IEEE Wireless Commun. Lett._ , vol. 9, no. 5, pp. 633–637, May 2020.