Graduate Student Member, IEEE Jingzhi Hu
email: jingzhi.hu@pku.edu.cn

Member, IEEE, Kaigui Bian, Senior Member, IEEE Hongliang Zhang
email: hongliang.zhang92@gmail.com

Fellow, IEEE Marco Di Renzo
email: marco.direnzo@centralesupelec.fr

Fellow, IEEE Zhu Han
email: hanzhu22@gmail.com

Fellow, IEEE Lingyang Song
email: lingyang.song@pku.edu.cn

K Bian

MetaSensing: Intelligent Metasurface Assisted RF 3D Sensing by Deep Reinforcement Learning

Keywords: RF 3D sensing, metasurface, deep reinforcement learning, policy gradient algorithm, beamformer pattern design

Using RF signals for wireless sensing has gained increasing attention. However, due to the unwanted multi-path fading in uncontrollable radio environments, the accuracy of RF sensing is limited. Instead of passively adapting to the environment, in this paper, we consider the scenario where an intelligent metasurface is deployed for sensing the existence and locations of 3D objects. By programming its beamformer patterns, the metasurface can provide desirable propagation properties. However, achieving a high sensing accuracy is challenging, since it requires the joint optimization of the beamformer patterns and mapping of the received signals to the sensed outcome. To tackle this challenge, we formulate an optimization problem for minimizing the cross-entropy loss of the sensing outcome, and propose a deep reinforcement learning algorithm to jointly compute the optimal beamformer patterns and the mapping of the received signals. Simulation results verify the effectiveness of the proposed algorithm and show how the sizes of the metasurface and the target space influence the sensing accuracy.

I. INTRODUCTION

Recently, leveraging widespread radio-frequency (RF) signals for wireless sensing applications has attracted growing research interest. Different from methods based on wearable devices or surveillance cameras, RF sensing techniques need no direct contact with the sensing targets [START_REF] Kianoush | Device-free RF human body fall detection and localization in industrial workplaces[END_REF].

The basic principle behind RF sensing is that the influence of the target objects on the propagation of wireless signals can be potentially recognized by the receivers [START_REF] Lee | Wireless sensing without sensors -An experimental approach[END_REF]. RF sensing techniques can be widely applied to many scenarios of daily life, such as surveillance [START_REF] He | Vigilnet: An integrated sensor network system for energy-efficient surveillance[END_REF], crowd sensing [START_REF] Ota | Quoin: Incentive mechanisms for crowd sensing networks[END_REF], ambient assisted living [START_REF] Cook | Assessing the quality of activities in a smart environment[END_REF], and remote health monitoring [START_REF] Amin | Radar signal processing for elderly fall detection: The future for in-home monitoring[END_REF]. In these applications, it is crucial to have high sensing accuracies.

Many RF-based sensing methods based on WiFi signals or millimeter wave signals have been proposed for sensing and recognizing human being and objects. In [START_REF] Zhang | On the feasibility of Wi-Fi based material sensing[END_REF], the authors designed an RF sensing system that can detect the location and type of moving objects by using Wi-Fi signals. In [START_REF] Jiang | Towards environment independent device free human activity recognition[END_REF], the authors proposed a deep learning based RF sensing framework that can remove environmental and subject-specific information and can extract environmental/subjectindependent features contained in the sensing data. In [START_REF] Hsu | Enabling identification and behavioral sensing in homes using radio reflections[END_REF], the authors designed a low-power RF sensing system that automatically collects behavior patterns of people.

In addition, using RF sensing to capture human beings and indoor scenes has being explored. In [START_REF] Adib | Capturing the human figure through a wall[END_REF][START_REF] Zhao | Rf-based 3d skeletons[END_REF], the authors used wide-band RF transceivers with multiple-input-multipleoutput (MIMO) antennas to capture images of human skeletons and showed that it is possible to reconstruct the human skeleton even when the RF signals are blocked by walls. In [START_REF] Pedross-Engel | Orthogonal coded active illumination for millimeter wave, massive-MIMO computational imaging with metasurface antennas[END_REF], the authors proposed to use mutually orthogonally coded millimeter wave signals to image the scenes including human beings and objects. However, using RF signals for sensing usually encompasses a signal collection and analysis process which passively accept the radio channel environment.

The radio environment is unpredictable and usually unfavorable, and thus the sensing accuracy of conventional RF sensing methods is usually affected by unwanted multi-path fading [START_REF] Honma | Human monitoring using MIMO radar[END_REF][START_REF] Li | Programmable radio environments with large arrays of inexpensive antennas[END_REF],

and/or unfavorable propagation channelsd from the RF transmitters to the receivers.

Intelligent metasurfaces have been proposed as a promising solution for turning unwanted propagation channels into favorable ones [START_REF] Di Renzo | Smart radio environments empowered by ai reconfigurable meta-surfaces: An idea whose time has come[END_REF][START_REF] Gacanin | Wireless 2.0: Towards an intelligent radio environment empowered by reconfigurable meta-surfaces and artificial intelligence[END_REF]. A metasurface is composed of a large number of electrically reconfigurable elements, which applies different phase-shifts on the RF signals that impinge upon it [START_REF] Basar | Wireless communications through reconfigurable intelligent surfaces[END_REF][START_REF] Zhang | Reflective-transmissive metasurface aided communications for full-dimensional coverage extension[END_REF]. By programming the reconfigurable elements, a metasurface deployed in the environment can change the RF propagation channel and create favorable signal beams for sensing [START_REF] Elmossallamy | Reconfigurable intelligent surfaces for wireless communications: Principles, challenges, and opportunities[END_REF]. We refer to the codings of the reconfigurable elements as the beamformer patterns. Through dynamically designing the beamformer patterns, a metasurface can actively control the RF signal beams in the sensing process, which potentially improves the sensing accuracy. Instead of employing complex and sophisticated RF transmitters and receivers [START_REF] Hashida | Intelligent reflecting surface placement optimization in air-ground communication networks toward 6G[END_REF], metasurface assisted RF sensing paves a new way of developing RF sensing methods, which have the capabilities of controlling, programming, and hence customizing the wireless channe.

In literature, the authors of [START_REF] Li | Machine-learning reprogrammable metasurface imager[END_REF] explored the use of metasurfaces to assist RF sensing and obtain 2D images for human beings. Besides, in [START_REF] Zhang | Towards ubiquitous positioning by leveraging reconfigurable intelligent surface[END_REF], the authors proposed a metasurface assisted RF system to obtain localization of mobile users. Nevertheless, no research works have tackled the analysis and design of metasurface assisted 3D RF sensing, which is more challenging to analyze and optimize than 2D RF sensing.

In this paper, we consider a metasurface assisted RF 3D sensing scenario, which can sense the existence and locations of 3D objects in a target space. Specifically, by programming the beamformer patterns, the metasurface performs beamforming and provides desirable RF propagation properties for sensing. However, there are two major challenges in obtaining high sensing accuracy in metasurface assisted RF sensing scenarios.

• First, the beamformer patterns of the metasurface need to be carefully designed to create favorable propagation channels for sensing.

• Second, the mapping of the received signals, i.e., the mapping from the signals received at the RF receiver to the sensing results of the existence and locations of the objects, needs to be optimized as well.

Nevertheless, the complexity of finding the optimal beamformer patterns is extremely high because the associate optimization problem is a discrete nonlinear programming with a large number optimization variables. Besides, the optimization of the beamformer patterns and the mapping of the received signals are closely coupled together, which makes optimizing the sensing accuracy in metasurface assisted RF sensing scenarios even harder.

To tackle these challenges, we formulate an optimization problem for sensing accuracy maximization by minimizing the cross-entropy loss of the sensing results with respect to the beamformer patterns and the mapping of the received signals. In order to solve the problem efficiently, we formulate a Markov decision process (MDP) for the optimization problem and propose a deep reinforcement learning algorithm. The proposed deep reinforcement learning algorithm is based on the policy gradient algorithm [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] and is referred to as the progressing reward policy gradient (PRPG) algorithm, since the reward function of the MDP is consistently being improved during the learning process. The computational complexity and the convergence of the proposed algorithm are analyzed. Moreover, we derive a non-trivial lower-bound for the sensing accuracy for a given set of beamformer patterns of the metasurface. Simulation results verify the effectiveness of the proposed algorithm and showcase interesting performance trends about the sensing accuracy with respect to the sizes of the metasurface and the target space. In particular, the contributions of this paper can be summarized as follows.

• We consider a metasurface assisted RF sensing scenario which can sense the existence and locations of objects in a 3D space. Then, we formulate an optimization problem to minimize the cross-entropy loss of the sensing results through optimizing the beamformer patterns and the mapping of the received signals. To this end, we adopt a MDP-based framework.

• We propose a deep reinforcement learning algorithm named PRPG to solve the formulated MDP. The complexity and the convergence of the proposed algorithm are analyzed, and a non-trivial lower-bound for the sensing accuracy is derived.

• We use simulation results to verify that the proposed algorithm outperforms other benchmark algorithms in terms of training speed and sensing accuracy. The simulation results unveil trends about the sensing accuracy as a function of the sizes of the metasurface and the target space, which gives insights on the implementation of practical metasurface assisted RF sensing systems.

The rest of this paper is organized as follows. In Section II, we introduce the model of the metasurface assisted RF sensing scenario. In Section III, we formulate the optimization problem to optimize the sensing accuracy by minimizing the cross-entropy loss of the sensing results. In Section IV, we formulate an MDP for the optimization problem and then proposed the PRPG algorithm to solve it. In Section V, the complexity and convergence of the PRPG algorithm are analyzed, and a lower-bound for the sensing accuracy is derived. Simulation results are provided in Section VI and conclusions are drawn in Section VII.

II. SYSTEM MODEL

In this section, we introduce the metasurface assisted 3D RF sensing scenario, which is illustrated in Fig. 1. In this scenario, there exist a pair of single-antenna RF transceivers, a metasurface, and a target space where the objects are located. The metasurface reflects and modifies the incident narrow-band signals at a certain frequency f c . The Tx unit and Rx unit of the transceiver keep transmitting and receiving at f c . The target space is a cubical region that is discretized into M equally-sized space grids. Each space grid is of size ∆l x × ∆l y × ∆l z .

The sensing process adopted in the considered scenario can be briefly described as follow.

The signals transmitted by the Tx unit are reflected and modified by the metasurface before entering into the target space. The modified signals are further reflected by the objects in the target space and received by the Rx unit. Then, the Rx unit maps the received signals to the sensing result, which indicates whether an object exists in each space grid.

In the following, we introduce the metasurface model in Subsection A, the channel model accounting for the metasurface in Subsection B, and the sensing protocol in Subsection C.

A. Metasurface Model

A metasurface is an artificial thin film of electromagnetic reconfigurable materials, which is composed of uniformly distributed reconfigurable elements [START_REF] Liu | Reconfigurable intelligent surfaces: Principles and opportunities[END_REF]. As shown in Fig. 1, the reconfigurable element of the metasurface are arranged in a two-dimensional array. By controlling the positive-intrinsic-negative (PIN) diodes coupled with each reconfigurable element, the reconfigurable element can adjust its electromagnetic response to the incident RF signals.

For each reconfigurable element, we refer to the different responses to incident RF signals as the reconfigurable element's configuration as in [START_REF] Dai | Reconfigurable intelligent surface-based wireless communications: Antenna design, prototyping, and experimental results[END_REF]. By changing the configuration of each reconfigurable element, the metasurface is able to modify the reflected signals and perform beamforming [START_REF] Di | Hybrid beamforming for reconfigurable intelligent surface based multi-user communications: Achievable rates with limited discrete phase shifts[END_REF].

We assume that each reconfigurable element has N S configurations, and each configuration of an element has a unique reflection coefficient for the incident RF signals. To be specific, we assume that each row and column of the metasurface contain the same number of reconfigurable elements, and the total number of reconfigurable elements is denoted by N . Based on [START_REF] Hu | Reconfigurable intelligent surface based RF sensing: Design, optimization, and implementation[END_REF], we denote the reflection coefficient of the n-th reconfigurable element corresponding to the incident signal from the TX unit and the reflected signal towards the m-th space grid by r n,m (c n ). Here, As shown in Fig. 1, the transmission channel from the Tx antenna to the Rx antenna is composed of three types of paths, i.e., the line-of-sight (LoS) path, the reflection paths, and the environmental scattering paths. The LoS path indicates the direct signal path from the Tx antenna to the Rx antenna. The reflection paths are the paths from the Tx antenna to the Rx antenna via the reflections from the metasurface and the objects in the target space. The environmental scattering paths account for the signals paths between the Tx antenna and the Rx antenna which involve complex reflection and scattering in the surrounding environment. Then, the equivalent baseband representation of the received signal containing the signals from all these three types of paths is denoted by y and can be expressed as

c n ∈ [1, N S ]
y = h los • √ P • x + M m=1 N n=1 h n,m (c n , ν m ) • √ P • x + h rl • √ P • x + σ, (1)
where P is the transmit power, and x denotes the transmitted symbol.

The component terms of (1) can be explained in detail as follows. The first term, i.e., h los •P •x, corresponds to the signal received in the LoS path, where h los denotes the gain. Based on [START_REF] Goldsmith | Wireless communications[END_REF],

h los can be expressed as

h los = λ 4π • √ g T g R • e -j2πd los /λ d los , ( 2
)
where λ is the wavelength of the signal, g T and g R denote the gains of the Tx and Rx antennas, respectively, and d los is the distance from the Tx antenna to the Rx antenna.

The second term in (1) corresponds to the signals that reach the Rx antenna via N • M reflection paths. In the second term, h n,m (c n , ν m ) denotes the gain of the reflection path via the n-th reconfigurable element in configuration c n and the m-th space grid with reflection coefficient ν m . Based on [START_REF] Di | Hybrid beamforming for reconfigurable intelligent surface based multi-user communications: Achievable rates with limited discrete phase shifts[END_REF][START_REF] Tang | Wireless communications with reconfigurable intelligent surface: Path loss modeling and experimental measurement[END_REF], h n,m (c n , ν m ) can be formulated as follows

h n,m (c n , ν m ) = λ 2 •r n,m (c n )•ν m • √ g T g R •e -j2π(dn+dn,m)/λ (4π) 2 • d n • d n,m , (3)
where d n denotes the distance from the Tx antenna to the n-th reconfigurable element and d n,m denotes the distance from the n-th reconfigurable element to the Rx antenna via the center of the m-th space grid.

Finally, the third and forth terms in (1) correspond to the signals from the environmental scattering paths and the additive noise at the Rx antenna, respectively. The symbol h rl ∈ C denotes the equivalent gain of all the environmental scattering paths, and σ is a random signal that follows the complex normal distribution, σ ∼ CN (0, ) with being the power of the noise.

Moreover, we refer to the vector of configurations selected for the N reconfigurable elements as a beamformer pattern of the metasurface, which can be represented by a N × N S -dimensional binary row vector c = ( ô(c 1 ), ..., ô(c N )). Specifically, ô(i) (∀i ∈ [1, N S ]) denotes the N Sdimensional row vector whose i-th element is 1 and the other elements are 0. Based on the definition of the beamformer pattern, the received signal in (1) can be reformulated as

y = h los • √ P • x + cAν • √ P • x + h rl • √ P • x + σ, (4)
where ν = (ν 1 , . . . , ν M ) denotes the vector of reflection coefficients of the M space grids, A = (α 1 , . . . , α M ) is referred to as the projection matrix, and α m = ( αm,1 , . . . , αm,N ) T with αm,n = (α m,n,1 , . . . , αm,n,N S ). Here, for all m ∈

[1, M ], n ∈ [1, N ], and i ∈ [1, N S ], αm,n,i
denotes the channel gain of the reflection path via the n-th reconfigurable element in configuration i and the m-the space grid with a unit reflection coefficient, which can be expressed as follows based on (3).

αm,n,i = λ 2 • r n,m (i) • √ g T g R (4π) 2 d n d n,m
• e -j2π(dn+dn,m)/λ .

C. RF Sensing Protocol

To describe the RF sensing process in the metasurface assisted scenario clearly, we formulate the following RF sensing protocol. In the protocol, the timeline is slotted and divided into cycles, and the Tx unit, the Rx unit, and the metasurface operate in a synchronized and periodic manner.

As shown in Fig. 2, each cycle consists of four phases: a synchronization phase, a calibration phase, a data collection phase, and a data processing phase. During the synchronization phase, the Tx unit transmits a synchronization signal to the metasurface and to the Rx unit, which identifies the start time of a cycle.

Then, in the calibration phase, the Tx unit transmits a narrow band constant signal, i.e., symbol x, at frequency f c . The metasurface sets the beamformer pattern to be c 0 = ( ô(1), . . . , ô(1)),

i.e., the N reconfigurable elements are in their first/default configuration. Besides, the received signal of the Rx unit is recorded as y 0 .

The data collection phase is divided into K frames that are evenly spaced in time. During this phase, the Tx unit continuously transmits the narrow band RF signal, while the metasurface changes its beamformer pattern at the end of each frame. As shown in Fig. 2, we denote the beamformer patterns of the metasurface corresponding to the K frames by binary row vectors c 1 , . . . c K . Specifically, the K beamformer patterns of the metasurface during the data collection phase constitutes the control matrix, which is denoted by C = (c T 1 , ..., c T K ) T . Besides, as c k is a binary row vector, control matrix is a binary matrix.

To remove the signal form the LoS path which contains no information of the target space, the received signals in the K frames are subtracted by y 0 . The K differences constitute the measurement vector, which is a noisy linear transformation of ν by the matrix Γ , i.e.,

ỹ = y -y 0 = Γ ν + σ, (6)
where

Γ = √ P •x•(C -C 0 )A with C 0 = (c T 0 , . . . , c T 0 )
T , y is a K-dimensional vector consisting of the sampled received signals during the K frames that can be calculated by ( 4), y 0 is a Kdimensional vector with all the elements being y 0 , and σ is the difference between the noise signals and environmental scattering signals of y and y 0 . In this article, we assume that the environment in the considered scenario is static or changing slowly. In this case, the signals from the environmental scattering paths, i.e., h rl • √ P • x is subtracted in [START_REF] Amin | Radar signal processing for elderly fall detection: The future for in-home monitoring[END_REF], and σ contains the difference between the Gaussian noise signals of y and y 0 . 1 Specifically, the k-th element of σ is σk ∼ CN (0, 2 ). We refer to ỹ as the measurement vector. Since Γ determines how the reflection characteristics of the objects are mapped to the measurement vector, we refer to Γ as the measurement matrix.

Finally, during the data processing phase, the receiver maps the measurement vector obtained in the data collection phase to the sensing results, which is a vector indicating the probabilities that objects exist in the M space grids. Given control matrix C, the mapping is modeled through a parameterized function, i.e., p = f w ( ỹ) with w being the parameter vector that is referred to as the mapping of the received signals. Moreover, the result of the mapping, i.e., p, is an M -dimensional real-valued vector. Specifically, its m-th element, i.e., pm ∈ [0, 1], indicates the probability that an object exists at the m-th space grid; therefore (1-pm ) indicates the probability that the m-th space grid is empty.

III. PROBLEM FORMULATION

In this section, we formulate the optimization problem for maximizing the sensing accuracy for the considered scenario. We adopt the cross-entropy loss as the objective function to measure the sensing accuracy, as minimizing the cross-entropy loss function can significantly improve the accuracy of classification and prediction [START_REF] Goodfellow | Deep Learning[END_REF]. In other words, the sensing accuracy is inversely proportional to the cross-entropy loss.

We define the cross-entropy loss in the considered scenario as

L CE = -E ν∈V M m=1 p m (ν) • ln(p m ) + (1 -p m (ν)) • ln(1 -pm ) , (7)
where V denotes the set of all possible reflection coefficient vectors corresponding to the existence of objects in the target space, and p m (ν) is a binary variable indicating the object existence in 1 If the environment is changing rapidly, h rl • √ P • x can be considered as an additional complex Gaussian noise [START_REF] Zhang | Reconfigurable intelligent surfaces assisted communications with limited phase shifts: How many phase shifts are enough?[END_REF], and σ in ( 6) is composed of the difference of the noise signals at the Rx and that of the environmental scattering signals, and thus its

variance is 2 + 2 hl .
the m-th space grid. Specifically, p m (ν) can be expressed as

p m (ν) =      0, if |ν m | = 0, 1, otherwise. (8)
In [START_REF] Zhang | On the feasibility of Wi-Fi based material sensing[END_REF], p is determined by f w ( ỹ). Generally, parameterized function f w ( ỹ) can take any form. For example, it can be a linear function, i.e., f w ( ỹ) = W ỹ + w , where W and w are determined by w and obtained by minimizing the mean squared error of the sensing results [START_REF] Boyd | Convex optimization[END_REF].

Besides, f w ( ỹ) can also be a nonlinear decision function, which determines the sensing results of ỹ by using conditional probabilities [START_REF] Mcdonough | Detection of signals in noise[END_REF]. In this paper, we consider that f w ( ỹ) is nonlinear and modeled as a neural network, where the elements of w stand for the weights of the connections and the biases of the nodes. We refer to the neural network for f w ( ỹ) as the sensing network.

The optimization problem for the metasurface assisted scenario that maximizes the sensing accuracy can be formulated as the following cross-entropy minimization problem, where the control matrix and the mapping of the received signals parameter are the optimization variables, i.e., (P1) : min

C,w L CE (C, w), (9)
s.t. (p 1 , ..., pM ) = f w ( ỹ), (10)
ỹ = √ P • x • (C -C 0 )A + σ, (11)
C = (c T 1 , ..., c T K ) T , (12)
c k = ( ô(c k,1 ), ..., ô(c k,N )), ∀k ∈ [1, K], (13)
c k,n ∈ [1, N S ], ∀k ∈ [1, K], n ∈ [1, N ]. (14)
In (P1), [START_REF] Hsu | Enabling identification and behavioral sensing in homes using radio reflections[END_REF] indicates that the objective is to minimize the cross-entropy loss by optimizing C and w. As p is determined by f w ( ỹ) and ỹ is determined by control matrix C, L CE defined in [START_REF] Zhang | On the feasibility of Wi-Fi based material sensing[END_REF] can be expressed as a function of C and w. Constraint [START_REF] Adib | Capturing the human figure through a wall[END_REF] indicates that the probabilities for the M space grids to contain objects are calculated by the mapping of the received signals, i.e., f w ( ỹ). Constraint [START_REF] Zhao | Rf-based 3d skeletons[END_REF] indicates that the measurement vector is determined by control matrix C as in [START_REF] Amin | Radar signal processing for elderly fall detection: The future for in-home monitoring[END_REF]. Besides, constraints ( 12)∼( 14) are due to the definition of the control matrix in Section II-C. Since the control matrix is a binary matrix and w is a real-valued vector, (P1) is a mixed-integer optimization problem and is NP-hard. 14). ( 16)

In (P2), we minimize the cross-entropy loss by optimizing w given C, and in (P3), we minimize the cross-entropy loss by optimizing C given w. Based on the alternating optimization technique [START_REF] Bezdek | Convergence of alternating optimization[END_REF], a locally optimal solution of (P1) can be solved by iteratively solving (P2) and (P3).

Nevertheless, given w, (P3) is still hard to solve due to the large number of integer variables in the control matrix. Moreover, the number of iterations for solving (P2) and (P3) can be large before converging to the local optimum of (P1). If traditional methods, such as exhaustive search and branch-and-bound algorithms, are applied, they will result in a high computational complexity. To solve (P2) and (P3) efficiently, we develop an MDP framework and solve it by proposing an PRPG algorithm, which are discussed in the next section. Furthermore, the convergence of the proposed algorithm to solve (P1) is analyzed in Section V.

IV. ALGORITHM DESIGN

In this section, we formulate an MDP framework for (P2) and (P3) in Subsection A and propose a deep reinforcement learning algorithm named PRPG to solve it in Subsection B.

A. MDP Formulation

In (P3), the optimization variable C is composed of a large number of binary variables satisfying constraints ( 12)∼( 14), which makes (P3) an integer optimization problem which is NP-hard and difficult to solve. Nevertheless, the metasurface can be considered as an intelligent agent who determines the configuration of each reconfigurable element for each beamformer pattern sequentially, and is rewarded by the negative cross-entropy loss. In this regard, the integer optimization problem (P3) can be considered as a decision optimization problem for the metasurface, which can be solved efficiently by the deep reinforcement learning technique, since it is efficient to solve highly-complexed decision optimization problems for intelligent agents [START_REF] Volodymyr | Human-level control through deep reinforcement learning[END_REF][START_REF] Li | Deep reinforcement scheduling for mobile crowdsensing in fog computing[END_REF]. As the deep reinforcement learning algorithm requires the target problem to be formulated as an MDP, we formulate (P2) and (P3) as an MDP, so that we can solve them by proposing an efficient deep learning algorithm.

An MDP encompasses an environment and an agent, and consists of four components: the set of states S, the set of available actions A, the state transition function T , and the reward function R [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. The states in S obey the Markov property, i.e., each state only depends on the previous state and the adopted action. Suppose the agent takes action a in state s, and the consequent state s is given by the transition function T , i.e., s = T (s, a). After the state transition, the agent receives a reward that is determined by reward function R, i.e., R(s , s, a).

To formulate the MDP framework for (P2) and (P3), we view the metasurface as the agent, and the RF sensing scenario including the surroundings, the RF transceiver, and the objects in the target space are regarded, altogether, as the environment. We consider the state of the metasurface the current control matrix, i.e., C and the action of the metasurface as selecting the configuration of a reconfigurable element for a beamformer pattern. Thus, actions of the metasurface determine the elements in control matrix C. Therefore, the next state of the MDP is determined by the current state and the action, and the Markov property is satisfied. In the following, we describe the components of the MDP framework in detail.

State: In the MDP of the metasurface assisted RF sensing scenarios, the state of the environment is defined as

s = (k, n, C), (17)
where k ∈ enters the terminal state of the MDP. For the non-terminal states, the elements of state s given s and a can be expressed as follows

= (k , n , C ), if (k, n) = (K, N ). Or, if (k, n) = (K, N ), the agent
k = k + 1, n = mod(n + 1, N ) + 1, (18)
(C ) k ,n =      (C) k ,n , if (k , n ) = (k, n), ô(a) if (k , n ) = (k, n), (19) ∀k
∈ [1, K], n ∈ [1, N ].
An example of the state transition is illustrated in Fig. 3, where N S = 2, K = 2, and N = 1.

In Fig. 3, the red dotted box indicates the element of C that is determined by the action in the current state. If (k, n) = (3, 1), it can be observed that all the configurations of the control matrix have been determined, and the MDP transits into the terminal states, where control matrix is denoted by C t .

Reward Function: In general MDP frameworks, the reward is a value obtained by the agent from the environment and quantifies the degree to which the agent's objective has been achieved [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. The reward for the agent is defined as the negative cross-entropy loss of the mapping of the received signals given the control matrix determined in the terminal states. If the terminal state has not been reached, the reward for the state transition is set to be zero.

Specifically, given parameter w, the reward in state s is defined as

R(s|w) =      -L CE (C t , w), if s is a terminal state, 0, otherwise. (20)
In the formulated MDP, the metasurface aims for obtaining an optimal policy to obtain the maximum reward in the terminal states. To be specific, the policy of the agent is a mapping from the state set to the available action set, i.e., π : S → A. To define the optimal policy π * , we first define the state-value function given policy π and parameter vector w, which indicates the accumulated reward of the agent via a certain state. Based on [START_REF] Hashida | Intelligent reflecting surface placement optimization in air-ground communication networks toward 6G[END_REF], the state-value function can be expressed as

V (s|π, w) =      -L CE (C, w), if s is a terminal state, V (s |π, w)| s =T (s,π(s)) , otherwise, (21)
The state-value function for π in state s indicates the accumulated rewards of the agent after state s. Based on ( 21), the state-value function for the initial state can be expressed as

V (s 0 |π, w) = -L CE (C π t , w), (22)
where C π t denotes the terminal state of the metasurface adopting policy π. Therefore, given parameter vector w, the optimal policy of the agent in the MDP framework is given by

π * (w) = arg max π V (s 0 |π, w) ⇐⇒ arg min C L CE (C, w). (23)
In [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], it can be observed that finding the optimal policy of the agent in the formulated MDP framework is equivalent to solving the optimal control matrix for (P3). Besides, solving (P2) is equivalent to solving the optimal w given the policy π.

B. Progressing Reward Policy Gradient Algorithm

To jointly solve (P2) and (P3) under the formulated MDP framework, we propose a novel PRPG algorithm. The proposed algorithm can be divided into two phase, i.e., the action selection phase and the training phase, which proceed iteratively.

1) Action Selection Process:

In the proposed algorithm, the agent, i.e., the metasurface, starts from the initial state s 0 and adopts the policy for selecting action in each state until reaching the terminal state. To select the current action in each state, the metasurface use policy π that maps the current state to a probability vector. To be specific, for a given state s, the policy results in an N S -dimensional probability vector denoted by π(s|w), which we refer to as the policy function. The i-th element of π(s|w) (i ∈ [1, N S ]), i.e., π i (s|w), is in range [0, 1] and denotes the probability of selecting the action a i in state s. Besides, π(s|w

) (i ∈ [1, N S ]) satisfies N S i=1 π i (s|w) = 1.
However, since the state contains the current control matrix that contains K • N • N S binary variables, the agent faces a large state space, and the policy function is hard to be modeled by using simple functions. To handle this issue, we adopt a neural network to model the policy function as neural networks are a powerful tool to handle large state space [START_REF] Zappone | Model-aided wireless artificial intelligence: Embedding expert knowledge in deep neural networks for wireless system optimization[END_REF]. The adopted neural network is referred to as the policy network, and we train the policy network by using the policy gradient algorithm [START_REF] Volodymyr | Human-level control through deep reinforcement learning[END_REF]. Specifically, the policy network is denoted by π θ (s|w), where θ denotes the parameters of the policy network and comprises the connection weights and the biases of the activation functions in the neural network.

The structure of the policy network is shown in Fig. 4. In state s, k and n are embedded as a K-dimensional and an N -dimensional vectors, respectively, where the k-th and n-th elements in the vectors are ones and the other elements are zeros. Specifically, we refer to the resulted vectors as the one-hot vectors. As for C, since the RF sensing for the target space is determined by CA as shown by (4), we first divide C to its real and imaginary parts and right-multiply them by the real and imaginary parts of A, respectively. Then, driven by the concept of modelbased learning [START_REF] Zappone | Wireless networks design in the era of deep learning: Model-based, ai-based, or both?[END_REF], we process the result, i.e., CA, by multi-layer perceptrons (MLPs). Besides, since the K beamformer patterns are symmetric in their physical meaning and changing their order does not impact the sensing performance, the MLPs that extract feature vectors from c 1 to c K need to be symmetric. This can be achieved by utilizing two symmetric MLP groups, each containing K MLPs with shared parameters. This significantly reduces the number of parameters and thus facilitates the training of the policy network. The sizes of the MLPs are labeled in Fig. 4.

For example, (2M, 512, 256) indicates that each MLP in a symmetric group that has three layers whose sizes are 2M , 512, and 256, respectively. Then, the one-hot vectors and the 2K extracted feature vectors are connected and input to the final MLP. The result of the final MLP is fed into the softmax layer which produces an N S -dimensional vector indicating the probability of selecting the N S actions.

Training of the Policy Network:

To collect the training data for the policy network, a replay buffer is adopted in order to store the experiences of the agent during state transitions. The replay buffer of the agent is denoted by B = {e}. The stored experience in the replay buffer is given by e = (s, a). It is worth noting that, differently from the replay buffer in traditional deep reinforcement learning algorithms [START_REF] Volodymyr | Human-level control through deep reinforcement learning[END_REF], the experience in the replay buffer does not record the reward obtained during the state transitions. This is because the rewards are determined by the current mapping of the received signals, which changes as w being updated. Thus, we propose that the rewards are calculated when the training process is invoked, instead of being recorded in the replay buffer.

We define a training epoch (or epoch in short) as the state transition process from the initial state to a terminal state. The experience of the agent within an epoch is stored into the replay buffer and used for training, which is discarded after being used. Based on the policy gradient theorem [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], in the training process, the gradient of V (s 0 |π, w) with respect to θ satisfies

∇ θ V (s 0 |π, w) ∝ E B,π θ V (T (S t , A t )|θ, w) ∇ θ π θ At (S t |w) π θ At (S t |w) , (24)
where (S t , A t ) ∈ B are the samples of the state and action in the replay buffer of an agent following policy π θ , and Q(S t , A t |θ, w) denotes the reward for the agent after selecting the action A t in S t and then following π θ . To calculate the gradient in [START_REF] Liu | Reconfigurable intelligent surfaces: Principles and opportunities[END_REF], the rewards for the agent in [START_REF] Hashida | Intelligent reflecting surface placement optimization in air-ground communication networks toward 6G[END_REF] need to be calculated. If s is a terminal state, the reward R(s|w) is calculated by using the Monte Carlo methods [START_REF] Rubinstein | Simulation and the Monte Carlo Method[END_REF],

i.e.,

R(s|w) = - ν∈V Nmc i=1 M m=1 p m (ν) ln(p m ) + (1 -p m (ν)) ln(1 -pm ) p=f w (Γ ν+ σi ) . (25)
Otherwise, R(s|w) = 0. In [START_REF] Dai | Reconfigurable intelligent surface-based wireless communications: Antenna design, prototyping, and experimental results[END_REF], N mc indicates the number of sampled noise vectors, and σi is the i-th sampled noise vector. As the rewards in the non-terminal states are zero, V (T (S t , A t )|θ, w) is equal to the reward at the final state for S t , A t , and policy π θ .

Specifically, in [START_REF] Dai | Reconfigurable intelligent surface-based wireless communications: Antenna design, prototyping, and experimental results[END_REF], p is generated by the sensing network, which is shown in Fig. 5. The sensing network consists of two parts, i.e., the model-aided decoder and an MLP. Firstly, the received vector is left-multiplied by the pseudo inverse of Γ , which is denoted by Γ + and can be calculated based on [START_REF] Bailyn | Generalized inversion[END_REF]. According to the least-square method [START_REF] Boyd | Convex optimization[END_REF], the model-aided decoder, i.e., ν = Γ + y, is the optimal linear decoder that results in the minimum mean square error (MSE) for the actual reflection vector ν, and thus can potentially increase the sensing accuracy of the sensing network. Then, ν is fed into a fully-connected MLP, which reconstructs the probability vector p.

In each process, θ is updated as follows

θ = θ + α • E e∈B V (T (S t , A t )|θ, w) ∇ θ π θ At (S t |w) π θ At (S t |w) , (26)
where the gradient ∇ θ π θ At (S t |w) is calculated by using the back-propagation algorithm [START_REF] Pineda | Generalization of back-propagation to recurrent neural networks[END_REF], and α denotes the training rate.

Training of the Sensing Network: After updating θ, the training of the sensing network is executed. The calculated rewards from [START_REF] Dai | Reconfigurable intelligent surface-based wireless communications: Antenna design, prototyping, and experimental results[END_REF] are used to train the sensing network which reduces the cross-entropy loss. To be specific, the loss function used to train the sensing network can be expressed as follows, which is in accordance with the objective function in the optimization problem (P2), i.e.,

L I (w) = E (s,a)∈B [R(s|w)]. (27)
algorithm are independent of the specific channel model, the proposed problem formulation and algorithm can also be adopted for the scenarios to optimize the sensing performance of the general RF sensing scenarios with multiple metasurfaces.

V. ALGORITHM ANALYSIS

In this section, we analyze the computational complexity and the convergence of the proposed algorithm in Subsections A and B, respectively. In addition, in Subsection C, we derive a nontrivial lower-bound for the sensing accuracy based on an upper-bound for the cross-entropy loss given a control matrix.

A. Computational Complexity

Since the PRPG algorithm consists of two main phases, i.e., the action selection phase and

the training phase, we analyze their respective computational complexities. The computational complexities are analyzed with regard to the number of beamformer patterns, K, the number of reconfigurable elements, N , the number of available configuration, N S , and the number of space grids, M .

1) Complexity of the Action Selection Phase:

In the proposed algorithm, the computationally most expensive part is the estimation of the action probabilities of the policy network. For each action selection phase, the computational complexity is given in Theorem 1.

Theorem 1: (Computational Complexity of the Action Selection Phase) In the PRPG algorithm, for the agent in each state, the complexity to calculate the action probabilities and determine the action is O(KN N S M ).

Proof 1: See Appendix A.

2) Complexity of the Training Process:

The computational complexity of ( 25) is provided in Lemma 1.

Lemma 1: The computational complexity of the reward calculation in [START_REF] Dai | Reconfigurable intelligent surface-based wireless communications: Antenna design, prototyping, and experimental results[END_REF] is

O KN N S M + K 2 M + M 2 .
Proof 2: See Appendix B

The computational complexities of training the policy network and the sensing network are given in Lemma 2.

B. Convergence Analysis

The detailed convergence analysis of the PRPG algorithm is based on the convergence analysis of the block stochastic gradient (BSG) algorithm. We denote w by x 1 and denote θ by x 2 , and thus the objective function in (P1) can be denoted by F (x 1 , x 2 ) = L CE (C π θ t , w), where C π θ t indicates the control matrix in the terminal state for the metasurface with policy π θ . Based on [START_REF] Xu | Block stochastic gradient iteration for convex and nonconvex optimization[END_REF], a BSG algorithm for solving (P1) is formulated as Algorithm 2, whose convergence analysis can be given by Lemma 3.

Lemma 3: Algorithm 2 converges to a locally optimal x * 1 and x * 2 as the number of iterations N itr → ∞, given that the following conditions are satisfied:

1) There exist a constant c and a constant ε such that, for each iteration indexed by j, the inequalities

E[g j i -∇ x i F (x 1 , x 2 )] 2 ≤ c • max i (α j i ) and E[ gj i -∇ x i F (x 1 , x 2 ) 2 ] ≤ ε 2 , i = 1, 2 are fulfilled.
2) There exists a uniform Lipschitz constant > 0 such that i=1,2

∇ x i F (x 1 , x 2 )-∇ x i F (x 1 , x 2 ) 2 2 ≤ 2 i=1,2 x i -x i 2 2 .
3) There exists a constant ψ such that E[

x j 1 2 2 + x j 2 2
2 ] ≤ ψ 2 , ∀j. Proof 5: Please refer to Corollary 2.12 in [START_REF] Xu | Block stochastic gradient iteration for convex and nonconvex optimization[END_REF], where the assumptions required in Corollary 2.12 in [START_REF] Xu | Block stochastic gradient iteration for convex and nonconvex optimization[END_REF] are equivalent to the three conditions in Lemma 3.

Comparing Algorithms 1 and 2, we can observe that the only difference between the two algorithms is in the functions for updating parameters. Nevertheless, solving the minimization problem [START_REF] Zhang | Reconfigurable intelligent surfaces assisted communications with limited phase shifts: How many phase shifts are enough?[END_REF], we can derive that ( 30) is equivalent to that

x j i = x j-1 i -α j i gj i . ( 29
)
As the learning rate sequence {α j i } j in Algorithm 2 can be arbitrarily selected, the parameter update of Algorithms 1 and 2 are essentially equivalent. In this regard, the proposed PRPG algorithm can be categorized as an BSG algorithm, whose convergence analysis follows Lemma 3.

However, since neural networks are encompassed in the mapping of the received signals and the policy function, the conditions in Lemma 3 are hard to be proven theoretically. Therefore, in additional to the theoretical analyses provided above, we also analyze the convergence through practical simulations in Section VI.

Moreover, the obtained solution by the proposed deep learning algorithm is a locally optimal solution of (P1). As shown in Algorithm 1, we iteratively solve (P2) and (P3) by updating θ using [START_REF] Di | Hybrid beamforming for reconfigurable intelligent surface based multi-user communications: Achievable rates with limited discrete phase shifts[END_REF] and updating w using [START_REF] Goldsmith | Wireless communications[END_REF], respectively. Based on the Q-learning algorithm [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], updating θ with the aim to maximize the total reward is equivalent to finding C minimizing L CE given w. Besides, it can be observed that updating w directly minimizes L CE given C. When the iteration terminates, updating the variables of C or w will not lead to a lower objective function value, i.e., the cross-entropy loss. Therefore, the solution obtained by the proposed Algorithm 1 is a locally optimal solution of the original problem (P1).

C. Lower Bound for Sensing Accuracy

In this section, we compute a lower-bound for the sensing accuracy in (P2) given control matrix C. To derive a lower bound, we assume that the mapping of the received signals maps the received RF signals to the sensing results by using an optimal linear decoder and a threshold judging process. In the following, we first provide the detection criterion for sensing, and then derive a lower-bound for sensing accuracy by leveraging an upper-bound for the cross-entropy loss.

1) Detection Criterion for Sensing: The reconstructed reflection coefficient vector from the linear decoder can be expressed as

ν = Γ + ỹ = Γ + Γ ν + Γ + σ. (30)
Algorithm 2: BSG algorithm for solving (P1)

Input: Starting point x 0 i , i = 1, 2; Learning rate sequence {α j i ; i = 1, 2} j=1,2,... ; Maximum number of iterations N itr ; Monte Carlo sampling size of the random noise N mc .

Output: Optimized x * 1 and x * 2 for (P1). for j = 1, 2, ..., N itr do for i = 1, 2 do Compute sample gradient for the w in the j-th iteration by gj

i = ∇ xi F (x j <i , x (j-1) ≥i
)

Update parameter x i by

x j i = arg min xi (g j i ) T (x i -x j-1 i ) + 1 2α j i x i -x j-1 i 2 2 . Output (x Nitr 1 , x Nitr 2 ) as (x * 1 , x * 2 );
Based [START_REF] Zhang | Reconfigurable intelligent surfaces assisted communications with limited phase shifts: How many phase shifts are enough?[END_REF], we analyze the probability distribution of the random variable νm , i.e., the m-th element of ν. We denote the m-th row vectors of Γ + and Γ + Γ as γ m and ξ m , respectively.

Then, νm = ξ m ν + γ m σ. The emptiness of the space grids other than the m-th space grid is modeled by the vector q -m , where q -m,m = 0 and 1 indicate that the m space grid is empty and nonempty, respectively, (m ∈ [1, M ], m = m). When the m-th space grid is empty (or nonempty), we denote the probability density functions (PDFs) of the real and imaginary parts of νm , i.e., νR,m and νI,m , by P 0 R,i (x) and P 0 I,i (x) (or P 1 R,i (x) and P 1 I,i (x)), respectively. We judge the emptiness of the m-th space grid according to the sum of νR,m and νI,m , i.e., µ m = νR,m + νI,m . When the m-th space grid is empty, given q -m , the sum of νR,m and νI,m , i.e., µ m , follows a normal distribution, i.e., µ m ∼ N (0, 0 m (q -m )), where

0 m (q -m ) = m =m, m ∈M q -m,m • ref,m • ( ξ R,m 2 + ξ I,m 2 ) + m ∈M • ( γ R,m 2 + γ I,m 2 ). (31)
Here, M is the set of indexes of M space grids, and subscripts R and I indicate the real and imaginary parts of a vector, respectively. The first summation term in [START_REF] Goodfellow | Deep Learning[END_REF] corresponds to the variance due to the reflection coefficients at the space grids other than the m-th space grid, and the second summation term in [START_REF] Goodfellow | Deep Learning[END_REF] corresponds to the variance due to the noise at the Rx unit.

On the other hand, when the q-th space grid is nonempty, the variance due to reflection coefficient of the m-th space grid needs to be added. Denote the variance of the reflection coefficient of the m-th space grid by ref,m , and the variance of µ m can be expressed as

1 m (q -m ) = 0 m (q -m ) + ref,m • ( ξ R,m 2 + ξ I,m 2 ). (32)
Given the emptiness of the m-th space grid, the PDF of µ m can be written as follows

P i m (x) = q -m ∈Q -m P m (q -m )P norm (x; 0, i m (q -m )), i = 0, 1 (33)
where Q -m indicates the set of all possible q -m , P norm (x; 0, i m (q -m )) (i = 0, 1) denotes the PDF of a normal distribution with zero mean and variance i m (q -m ), and P m (q -m ) denotes the probability for the existence indicated by q -m to be true, i.e.,

P m (q -m ) = m =m,m ∈M P r m (q -m,m ). (34)
Here, P r m (x) with x being 0 and 1 indicates the probabilities that the m -th space grid are empty and nonempty, respectively.

We use the difference between P 1 m (q -m ) and P 0 m (q -m ) as the judgement variable to determine whether the m-th space grid is empty or not. To facilitate the analysis, we adopt the log-sum as a substitute for the sum in [START_REF] Mcdonough | Detection of signals in noise[END_REF]. Therefore, the judgement variable can be calculated as

τ m = q -m ∈Q -m ln p m (q -m )P norm (x; 0, 1 m (q -m )) (35)
-

q -m ∈Q -m ln p m (q -m )P norm (x; 0, 0 m (q -m )) .
It can be observed from ( 35) that τ m increases as P 1 m (µ m ) increases, and that it decreases as P 0 m (µ m ) increases. Therefore, we can judge the emptiness of the m-th space grid through the value of τ m . Specifically, the sensing result of the m-th space grid is determined by comparing the judging variable τ m with the judging threshold, which is denoted by ρ m . If τ m ≤ ρ m , the sensing result of the m-th space grid is "empty", which is denoted by the hypothesis H 0 . Otherwise, if τ m > ρ m , the sensing result is "non-empty", which is denoted by the hypothesis H 1 . After simplifying [START_REF] Volodymyr | Human-level control through deep reinforcement learning[END_REF], the detection criterion for H 0 and H 1 can be expressed as

τ m = µ 2 m q -m ∈Q -m 1 m (q -m ) -0 m (q -m ) 2 1 m (q -m ) 0 m (q -m ) - 1 2 q -m ∈Q -m ln 1 m (q -m ) 0 m (q -m ) H 1 ≷ H 0 ρ m . (36)
Since µ 2 m > 0, the range of ρ m can be expressed [-

1 2 q -m ∈Q -m ln( 1 m (q -m ) 0 m (q -m ) ), ∞].
2) Upper Bound of Cross Entropy Loss: We analyze the cross-entropy loss incurred by the detection criterion in [START_REF] Li | Deep reinforcement scheduling for mobile crowdsensing in fog computing[END_REF], which can be considered as a non-trivial upper-bound for the crossentropy loss defined in [START_REF] Zhang | On the feasibility of Wi-Fi based material sensing[END_REF]. As the sensing result given by ( 36) is either 0 or 1, if the sensing result is accurate, the incurred cross-entropy loss will beln(1) = 0; otherwise, the incurred cross-entropy loss will beln(0) → ∞. In practice, the cross-entropy loss due to an inaccurate sensing result is bounded by a large number C In0 . Given H 0 (or H 1 ) being true, the probability for the sensing result to be inaccurate is the probability of τ m > ρ m , i.e., Pr{τ m > ρ m |H 0 } (or

Pr{τ m ≤ ρ m |H 1 }).
Denote the probability for an object to be at the m-th space grid by pm , and the cross-entropy loss of the m-th space grid can be calculated as

L m = C In0 • (1 -pm ) • Pr{τ m > ρ m |H 0 } + C In0 • pm • Pr{τ m ≤ ρ m |H 1 }, (37)
where Pr{τ m > ρ m |H 0 } and Pr{τ m ≤ ρ m |H 1 } can be calculated by using Proposition 1.

Proposition 1: The conditional probability for sensing the m-th space grid inaccurately can be calculated as follows

Pr{τ m > ρ m |H 0 } = Pr{µ 2 m > ρm |H 0 } = 1- q -m ∈Q -m P m (q -m )•erf ρm 2 0 m (q -m ) , (38)
Pr{τ m ≤ ρ m |H 1 } = Pr{µ 2 m ≤ ρm |H 1 } = q -m ∈Q -m P m (q -m )•erf ρm 2 1 m (q -m ) , (39)
where erf(•) denotes the error function [START_REF] Mcdonough | Detection of signals in noise[END_REF], and

ρm = 1 2 q -m ∈Q -m ln( 1 m (q -m )/ 0 m (q -m )) + ρ m q -m ∈Q -m 1 m (q -m )-0 m (q -m ) 1 m (q -m )• 0 m (q -m ) . ( 40
)
Proof 6: Based on (36), the judging condition τ m

H 1 ≷ H 0 ρ m is equivalent to µ 2 m H 1 ≷ H 0 ρm . Therefore, Pr{µ 2 m > ρm |H 0 } = Pr{τ m > ρ m |H 0 } and Pr{µ 2 m ≤ ρm |H 1 } = Pr{τ m ≤ ρ m |H 1 }. Also, given q -m , µ 2
m follows a chi-squared distribution with one degree of freedom. Therefore, the cumulative distribution function of µ 2 m is a weighted sum of error functions, and thus the conditional probabilities can be calculated by using [START_REF] Zappone | Wireless networks design in the era of deep learning: Model-based, ai-based, or both?[END_REF] and [START_REF] Rubinstein | Simulation and the Monte Carlo Method[END_REF].

Besides, we can observe in [START_REF] Zappone | Model-aided wireless artificial intelligence: Embedding expert knowledge in deep neural networks for wireless system optimization[END_REF] that L m is determined by the judgment threshold ρ m . Then, based on [START_REF] Zappone | Model-aided wireless artificial intelligence: Embedding expert knowledge in deep neural networks for wireless system optimization[END_REF] to [START_REF] Bailyn | Generalized inversion[END_REF], ∂L m /∂ρ m can be calculated as

∂L m /∂ρ m = - 2C In0 √ π • ∂ ρm ∂ρ m • q -m ∈Q -m P m (q -m ) • φ m (q -m ), (41)
φ m (q -m ) = (1-pm )•e -ρm/2 0 m (q -m ) 8 0 m (q -m )ρ m - pm • e -ρm/2 1 m (q -m ) 8 1 m (q -m )ρ m . (42)
Then, the optimal ρ * m can be obtained by solving ∂L m /∂ρ m = 0. Denoting the minimal L m corresponding to ρ * m as L * m , the upper bound for the cross-entropy loss in [START_REF] Zhang | On the feasibility of Wi-Fi based material sensing[END_REF] can be calculated as

L ub = m∈M L * m . (43)
When the emptiness of the space grids other than the m-th is given, the upper bound of the cross-entropy loss can be calculated from Proposition 2. Since the sensing accuracy is inversely proportional to the cross-entropy loss, a lower-bound for the sensing accuracy is derived.

Proposition 2: When the emptiness of the space grids other than the m-th is given, i.e.,

Q -m = {q -m }, the optimal judging threshold for the m-th space grid is

ρ * m (q -m ) =      1 2 ln( 0 m (q -m ) 1 m (q -m ) ), if pm > 1 m (q -m ) 0 m (q -m )+ 1 m (q -m ) , 2 ln( 1-pm pm ) -1 2 ln( 0 m (q -m ) 1 m (q -m ) ), otherwise. (44)
Proof 7: The sign of ∂L m /∂p m is determined by φ m (q -m ). We calculate the ratio between the two terms of φ m (q -m ), which can be expressed as

ι m (q -m ) = 1 -pm pm • 1 m (q -m ) 0 m (q -m ) • e -ρm• 1 m (q -m )-0 m (q -m ) 2 0 m (q -m )• 1 m (q -m ) . (45)
Since 1 m (q -m ) > 0 m (q -m ) and ρm ∝ ρ m , ι m (q -m ) is a monotonic decreasing function with respect to ρ m and ι m (q -m ) ≥ 0. Also, φ m (q -m ) ≥ 0 ⇐⇒ ι m (q -m ) ≥ 1, and thus, ∂L m /∂p m ≥ 0 if and only if ι m (q -m ) ≥ 1. Therefore, the minimal H m is obtained when ρ m satisfies the condition ι m (q -m ) = 1. Then, we can prove Proposition 2 by solving ι m (q -m ) = 1 and considering that ρ m ≥ - 1 2 ln(

1 m (q -m ) 0 m (q -m )
). However, since the number of possible q -m can be large, (typically, |Q -m | = 2 M -1 ), calculating the exact ∂L m /∂ρ m in ( 41) is time-consuming, which makes it hard to find the exact ρ * m and L * m . Therefore, in practice, we approximate H ub by using a random sampled subset of Q sam -m , which is denoted by Q sam -m ⊂ Q -m . Moreover, since the sign of ∂L m /∂ρ m is determined by the sum of φ m (q -m ), and φ m (q -m ) has a zero point, which can be calculated by [START_REF] Skiena | Sorting and searching[END_REF]. If ρ m is less than the zero point of φ m (q -m ), φ m (q -m ) ≥ 0; and otherwise φ m (q -m ) < 0. Therefore, we use the mean of the optimal ρ * m (q -m ) for each q -m ∈ Q sam -m to estimate ρ * m , and approximate the upper-bound accordingly. The estimated ρ * m is denoted by ρ * m , which can be formulated as follows

ρ * m = 1 |Q sam -m | q -m ∈Q sam -m ρ * m (q -m ), (46)
where ρ * m (q -m ) can be obtained by Proposition 2. When |Q sam -m | is large enough, ρ * m in ( 46) can approximate ρ * m . Finally, given the approximated upper bound of the cross-entropy loss as Lub , then it can be observed from (37) that the upper bound of average probability of sensing error for a space grid is P err,ub = Lub /C In0 . Therefore, the lower bound of the average sensing accuracy for a space grid is P acc,lb = 1 -P err,ub .

VI. SIMULATION AND EVALUATION

In this section, we first describe the setting of the simulation scenario and summarize the simulation parameters. Then, we provide simulation results to verify the effectiveness of the proposed PRPG algorithm. Finally, using the proposed algorithm, we evaluate the cross-entropy loss of the metasurface assisted RF sensing scenario with respect to different numbers of sizes of the metasurface, and numbers of space grids. Besides, we also compare the proposed method with the benchmark, i.e., the MIMO RF sensing systems.

A. Simulation Settings

The layout of the considered scenario is provided in Fig. 6. The metasurface adopted in this paper is the same as the one used in [START_REF] Hu | Reconfigurable intelligent surface based RF sensing: Design, optimization, and implementation[END_REF], and the reflection coefficients of the reconfigurable

T g R P G f c N S K p m,1 |V| M Q sam -m ǫ α 0 ǫ ref element in different configurations are simulated in CST software, Microwave Studio, Transient
Simulation Package [START_REF] Hirtenfelder | Effective antenna simulations using CST MICROWAVE STUDIO[END_REF], by assuming 60 • incident RF signals with vertical polarization. Besides, to increase the reflected signal power in the simulation, we combine G reconfigurable elements as an independently controllable group. The reconfigurable elements of an independently controllable group are in the same configuration, and thus they can be considered as a single one. Therefore, the proposed algorithm is suitable for this case. The number of independently controllable group is denoted by N G .

The origin of the coordinate is at the center of the metasurface, and the metasurface is in the y-z plane. In addition, the z-axis is vertical to the ground and pointing upwards, and the xand y-axes are parallel to the ground. The Tx and Rx antennas are located at (0.87, -0.84, 0) m and (0, 0, -0.5) m, respectively. The target space a cuboid region located at 1 m from the metasurface, and is divided into M space blocks each with size 0.1 × 0.1 × 0.1 m 3 . The simulation parameters are summarized in Table I.

B. Results

In Fig. 7, we compare the training results for different algorithms. Specifically, the first algorithm in the legend is the proposed PRPG algorithm where a sensing network (SensNet) and a policy network (PolicyNet) are adopted. The second algorithm adopts a sensing network but adopt a random control matrix. The third algorithm adopts both a sensing network and a policy It can be observed that the proposed PRPG algorithm converges with high speed and it results in the lowest cross-entropy loss among all the considered algorithms. In particular, Fig. 8 shows a ground-truth object and the corresponding sensing results versus the number of training epochs. As the number of training epochs increases, the sensing result approaches the ground truth and becomes approximately the same after 10 4 training epochs.

!"#$$%&'("#)*+,#$$ !"#$ !$#$ %#" $#$ $ %$$$ &$$$ '$$$ ($$$ !$$$$ -./0&"+#1+2"
In Fig. 9, it shows the ground-truths and the sensing results for different algorithms and the target objects with different shapes. Comparing the sensing results with the ground truths, we can observe that the proposed algorithm outperforms other benchmark algorithms to a large extent.

Besides, by comparing the sensing results of the proposed algorithm in the second column with !"#$$ '("#)*%+#$$% !" ! !" " !" #! " #""" $""" %""" &""" !"""" ,-./0"%#1%2"34'4'5%&)#67$ In Fig. 11, it can be observed that as the size of the metasurface, i.e., N G , increases, the result cross-entropy loss after training decreases. This is because the received energy can be improved with more reconfigurable elements to reflect transmitted signals, as indicated by (4).

! ! " #$ "# ! ! " #$ "$ ! ! " #$ "%
Besides, more reconfigurable elements create a larger design freedom and higher controllability of the beamforming, which makes gains of these reflection paths via different space grids more distinguishable. Therefore, objects at different space grids can be sensed with a higher precision.

However, the cross-entropy cannot be reduced infinitely. When N G is sufficiently large, the crossentropy will remains stable. As shown in Fig. 11, the cross-entropy loss results for N G = 9 and N G = 16 are almost the same. Besides, comparing the curves for N G = 9 and N G = 16 within the first 2000 training epochs, we can observe that increasing the number of reconfigurable elements when N G ≥ 9 has a negative impact on the training speed and convergence rate. This is because increasing the number of reconfigurable elements leads to a higher complexity of finding the optimal policy for the metasurface to determine its control matrix, since the policy network of the metasurface needs to handle a higher-dimensional state space. In Fig. 12, we compare the theoretical upper-bound derived in [START_REF] Petković | Generalized matrix inversion is not harder than matrix multiplication[END_REF] the proposed PRPG algorithm for different values of M in 2D and 3D scenarios. It can be observed that, in both 2D and 3D scenarios, the probability of sensing error increases with M . Also, the cross-entropy loss in 3D scenarios is higher than those for 2D scenarios. This is because the space grids in the 3D scenarios are more closely spaced to each other, which make them hard to be distinguished.

Finally, it can be observed that, as M increases, the cross-entropy loss of the proposed algorithm increases more quickly in 3D scenarios compared to that in 2D scenarios. This which verifies that 3D sensing is more difficult than 2D sensing.

In Fig. 13, we show the comparison between the proposed metasurface assisted scenario and the benchmark, which is the MIMO RF sensing scenarios with no metasurface. Both the metasurface assisted scenario and the MIMO scenarios adopted a similar layout described in

Fig. 1 .

 1 Fig. 1. Illustration of the metasurface assisted RF sensing scenario.

  denotes the configuration of the n-th reconfigurable element and c n ∈ Z, where Z denotes the set of integers.B. Channel ModelIn the metasurface assisted RF sensing scenario, the Tx unit and Rx unit adopt single antennas to transmit and receive RF signals. The Tx antenna is a directional antenna, which points towards the metasurface so that most of the transmitted signals are reflected by the metasurface and propagate into the target space. The signals reflected by the metasurface are reflected by the objects in the target space and then reach the Rx antenna. The Rx antenna is assumed to be omni-directional and located right below the metasurface, as shown in Fig.1. This setting ensures that the signals reflected by the metasurface are not directly received by the Rx antenna, and thus most of the received signals contain the information of the objects in the target space.

[ 1 ,

 1 K] and n ∈ [1, N ] are the row and column indexes for control matrix indicating the configuration that the metasurface aims to select. Besides, C in[START_REF] Basar | Wireless communications through reconfigurable intelligent surfaces[END_REF] denotes the current control matrix of the metasurface in state s. The initial state of the MDP framework is denoted bys 0 = (1, 1, C 0 ), where C 0 is the control matrix of the metasurface whose reconfigurable elements are in the first/default configuration. We refer to the states with indices (k, n) = (K + 1, 1) as the terminal states. When the terminal states are reached, all the configurations in the control matrix have been selected.Action: In each state s = (k, n, C), the metasurface selects the state of the n-th reconfigurable element in the k-th frame. The action set of the metasurface in each state can be expressed as A = {1, ..., N S }, where the j-th action (i ∈ [1, N S ]) indicates that the metasurface selects the target configuration to be the j-th configuration. In other words, the metasurface sets (C) k,n = ô(a), a ∈ A.State Transition Function: After the metasurface selects the action, the MDP framework transits into the next state, s

Fig. 3 .

 3 Fig. 3. Example of the state transition in the formulated MDP, with K = 2, N = 1, and NS = 2.

Fig. 4 .

 4 Fig. 4. Network structure of the policy network used in the proposed algorithm.

2 )

 2 Training Process: The purpose of the training process is two-fold: (a) To make the policy network improves the current policy in action selection based on (23). (b) To make the mapping of the received signals incur lower cross-entropy loss. Accordingly, the training process consists of two parts, i.e., training of the policy network and training of the sensing network. In the trainingof the policy network, we adopt the policy gradient method[START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. Besides, the training of the sensing network results in that the rewards for the terminal states progress during the training of the policy. Due to these characteristics, the proposed algorithm is named as progressing reward policy gradient algorithm.

Fig. 5 .

 5 Fig. 5. Sensing network of the metasurface.

Lemma 2 :Proof 3 :Proof 4 :

 234 After calculating the rewards, the complexity of the training the sensing network and the policy network are O(M 2 ) and O(N S (K + N + M )), respectively. If a single MLP is used to substitute the symmetric MLP group, the computational complexity of training the policy network is O(KM N S + N N S ). See Appendix C. It can be observed from Lemma 2 that using a symmetric MLP group instead of a single large MLP in the policy network can reduce the complexity of the training process. Based on Lemmas 1 and 2, the total computational complexity of each training process is provided in Theorem 2. Theorem 2: (Computational Complexity of the Training Process) The computational complexity of each training phase of the PRPG algorithm is O(KN N S M + K 2 M + M 2 ) . See Appendix D.

Fig. 6 .

 6 Fig. 6. Simulation layout.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Cross-entropy loss versus the number of training epochs for different algorithms.

Fig. 9 .

 9 Fig. 9. Illustrations of the ground-truths and the sensing results of objects with different shapes for different algorithms.

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Cross-entropy loss of the mapping of the received signals in high, normal, and low learning rate cases.

6 !Fig. 12 .

 612 Fig. 12. Estimated upper-bound and the results of the proposed algorithm for the cross-entropy loss versus different numbers of space grids in 2D and 3D scenarios. The drawings at the bottom indicate the arrangement of the space grids

Fig. 13 .

 13 Fig. 13. Comparison between the metasurface assisted scenario and the MIMO scenarios with different numbers of Tx/Rx antennas. The bars illustrate the results for different MIMO scenarios, and the dash lines depict the results of the metasurface assisted scenario with different numbers of frames.

TABLE I SIMULATION

 I PARAMETERS.

		Parameter		Value
		Tx antenna gain ( ) g		15.0 dBi
		Rx antenna gain ( )		6.0 dBi
		Tx power ( )		100 mW
	Number of reconfigurable elements per group ( )	144
		Signal frequency ( )		3.198 GHz
	Number of available states ( )		4
		Number of frames ( )		10
	Probability of space grid being nonempty (	)	0.5
	Size of reflection vector set ( )		100
		Number of space grids ( )		18
	Size of random sampled subset (	)	1000
		Power of noise ( )		10 -9 dBm
	Size of space of interest ( ! , " , # )		(0.1, 0.1, 0.1) m
		Initial learning rate ( )		0.001
	Variance of reflection coefficient ( )	1
	Parameter	Parameter		Parameter

for n ep = 1 to N ep do Set the current state to be the initial state, i.e., s = s 0 ; # Action selection phase while s is not a terminal state do Select the configuration of the n-th reconfigurable element in the k-th frame following the probability distribution given by π θ (s|w).

Set action a as the selected configuration, and enter into the transited state s = T (s, a);

Store experience e = (s, a) into replay buffer B;

# Training phase

Collect all the experiences from B, and calculate the reward for each sampled experience by using [START_REF] Dai | Reconfigurable intelligent surface-based wireless communications: Antenna design, prototyping, and experimental results[END_REF];

Update parameter θ and w by ( 26) and [START_REF] Goldsmith | Wireless communications[END_REF], respectively, where the learning rate

In each training process, w is updated by

where the gradient ∇ w L I (w) is calculated by using the back-propagation algorithm.

In summary, the proposed PRPG algorithm is summarized in Algorithm 1.

Remark: Using the proposed deep reinforcement learning technique enables our proposed algorithm to handle the complicated cases where multiple metasurfaces exist. Specifically, when the multiple metasurfaces are on the same plane, they can be considered as a whole, and thus the channel model in (1) needs no changes. When the multiple metasurfaces are on different planes, the channel model needs to be modified to adapt to the correlation between different metasurfaces, which is left for future work. Nevertheless, since the problem formulation and the proposed the metasurface and the target space on the cross-entropy loss, which provides insights on the implementation of practical metasurface assisted RF sensing systems.

APPENDIX A PROOF OF THEOREM 1

The complexities of embedding K and N as one-hot vectors is O(K) and O(N ), respectively.

Based on [START_REF] Skiena | Sorting and searching[END_REF], the complexity of multiplex the K beamformer patterns that are

For a fully connected neural network with a fixed number of hidden layers and neurons, the computational complexity of the backpropagation algorithm is proportional to the product of the input size and the output size [START_REF] Sipper | A serial complexity measure of neural networks[END_REF].

Therefore, the computational complexities of the symmetric MLP group and the Q-value MLP are

, respectively. As the connecting operation has complexity O(1)

and finding the maximum Q-value is O(N S ), the total computational complexity has complexity O(KN N S M ) and is therefore dominated by the matrix multiplication.

APPENDIX B PROOF OF LEMMA 1

We consider the worst case scenario for the computation, i.e., the former states in all the samples are terminal states. In this case, the rewards are calculated from [START_REF] Dai | Reconfigurable intelligent surface-based wireless communications: Antenna design, prototyping, and experimental results[END_REF]. The term inside the second summation consists of two part, i.e., the cross-entropy calculation which has computational complexity O(M ), and the calculation of p by using the sensing network. The computational complexity of calculating CA is O(KN N S M ).

Based on [START_REF] Petković | Generalized matrix inversion is not harder than matrix multiplication[END_REF], calculating the pseudo-inverse matrix Γ + , where Γ is a K × M matrix, has complexity O(K 2 M ). Similar to the analysis of the computational complexity of MLPs in the proof of Theorem 1, the computational complexity of the MLP is O(M 2 ). Therefore, the computational complexity of calculating

For a fully connected neural network with a fixed number of hidden layers and neurons, the computational complexity of the back-propagation algorithm is proportional to the product of the input size and the output size [START_REF] Sipper | A serial complexity measure of neural networks[END_REF]. Therefore, the computational complexity of using the back-propagation algorithm for updating the parameter vector of the sensing network is O(M 2 ).

The policy network can be considered as two connected MLPs: the first one takes the onehot embedding vectors of k and n as the input, and the second one takes the K measuring vectors with 2M dimensions as the input. Moreover, as a symmetric MLP group is considered, the actual size of the input vector for the second MLP is 2M instead of 2KM . Therefore, the computational complexity of training the first and second MLP of the policy network are

and O(N S M ), respectively, and the total computational complexity is thus

Furthermore, if a single large MLP with layer sizes (2KM, 64, 32K) is used to substitute the symmetric MLP group, the computational complexities of training the second MLP is O(KN S M ), and the total computational complexity of training the policy network is O(KM N S + N N S ). Therefore, Lemma 2 is proved.

APPENDIX D PROOF OF THEOREM 2

Based on ( 26) and ( 27), the complexity of calculating the loss functions are determined by the computation of the reward and action probabilities. From Theorem 1 and Lemma 2, it follows that the complexity of calculating the reward is of higher order than that of calculating the action probabilities. Therefore, the computational complexity of the training phase is dominated by the calculation of the N b rewards, which is O(KN N S M + K 2 M + M 2 ).