Online Learning for Orchestration of Inference in Multi-User End-Edge-Cloud Networks

Deep-learning-based intelligent services have become prevalent in cyber-physical applications including smart cities and health-care. Deploying deep-learning-based intelligence near the end-user enhances privacy protection, responsiveness, and reliability. Resource-constrained end-devices must be carefully managed in order to meet the latency and energy requirements of computationally-intensive deep learning services. Collaborative end-edge-cloud computing for deep learning provides a range of performance and efficiency that can address application requirements through computation offloading. The decision to offload computation is a communication-computation co-optimization problem that varies with both system parameters (e.g., network condition) and workload characteristics (e.g., inputs). On the other hand, deep learning model optimization provides another source of tradeoff between latency and model accuracy. An end-to-end decision-making solution that considers such computation-communication problem is required to synergistically find the optimal offloading policy and model for deep learning services. To this end, we propose a reinforcement-learning-based computation offloading solution that learns optimal offloading policy considering deep learning model selection techniques to minimize response time while providing sufficient accuracy. We demonstrate the effectiveness of our solution for edge devices in an end-edge-cloud system and evaluate with a real-setup implementation using multiple AWS and ARM core configurations. Our solution provides 35% speedup in the average response time compared to the state-of-the-art with less than 0.9% accuracy reduction, demonstrating the promise of our online learning framework for orchestrating DL inference in end-edge-cloud systems.

INTRODUCTION
Deep-learning (DL) is advancing real-time and interactive user services in domains such as autonomous vehicles, natural language processing, healthcare, and smart cities [35]. Due to user device resource constraints, deep learning kernels are often deployed on cloud infrastructure to meet computational demands [3]. However, unpredictable network constraints including signal strength and delays affect real-time cloud services [18]. Edge computing has emerged to complement cloud services, bringing compute capacity closer to the user-end devices [47]. A collaborative end-edge-cloud architecture is essential to provide deep-learning-based services with acceptable latency to user-end devices [30]. The edge paradigm increases offloading opportunities for resourceconstrained user-end devices. Offloading DL services in a 3-tier end-edge-cloud architecture is a complex optimization problem considering: (i) diversity in system parameters including heterogeneous computing resources, network constraints, and application characteristics, and (ii) dynamicity of DL service environment including workload arrival rate, user traffic, and multi-dimensional performance requirements (e.g., application accuracy, response time) [11,37,38].
Existing offloading strategies for DL tasks are based on the assumptions that (i) all DL tasks have similar compute intensity and require similar communication bandwidth, (ii) offloading improves performance, and (iii) latency is guaranteed with offloaded tasks. However, these assumptions do not hold in practice due to dynamically varying application and network characteristics, where the computation-communication and accuracy-performance tradeoffs are inconsistent and nontrivial [11,38,42]. Under varying system dynamics, such offloading strategies limit the gains from using the edge and cloud resources. Further, model optimization techniques such as quantization and pruning can reduce the computation complexity of DL tasks by sacrificing the model accuracy [9,40]. Considering model optimization techniques in conjunction with offloading provides opportunities to influence the computation-communication trade-off [41]. This exposes an alternative to offloading in resource constrained devices executing DL inference. Finding the optimal choice between offloading the DL tasks to edge and cloud layers and using optimized models for inference at local devices results in a high-dimensional optimization problem. Understanding the underlying system dynamics and intricacies among computation, communication, accuracy, and latency is necessary to orchestrate the DL services on multi-level edge architectures. Reinforcement learning is an effective approach to develop such an understanding and interpret the varying dynamics of such systems [29,32]. Reinforcement learning allows a system to identify complex dynamics between influential system parameters and make a decision online to optimize objectives such as response time [39]. We propose to employ online reinforcement learning to orchestrate DL services for multi-users over the end-edge-cloud system. Our contributions are: • Runtime orchestration scheme for DL inference services on multi-user end-edge-cloud networks. The orchestrator uses reinforcement learning to perform platform offloading and DL model selection at runtime to optimize response time provided accuracy requirements. • Implementation of our online learning solution on a real end-edge-cloud test-bed and demonstration of its effectiveness in comparison with state-of-the-art [36] edge orchestration strategies.

BACKGROUND
In this section, we present the relevant background and significance of orchestrating DL workloads on end-edge-cloud architecture.

Offloading DL Workloads in End-Edge-Cloud Architecture
Computation offloading techniques offload an application (or a task within an application) to an external device such as cloud servers [25]. Offloading is typically done in order to improve performance or efficiency of devices [3]. DL workloads on end-devices are conventionally offloaded to cloud servers, but delay-sensitive services for distributed systems rely on performing inference at the edge as an alternative [47]. Inference at the edge can provide cloud-like compute capability closer to the user devices, reducing data transmission and network traffic load. Edge offloading can provide relatively predictable and reliable performance compared to cloud offloading, as there is less workload and network variance [18] [16]. In the context of the end-edge-cloud paradigm, computation offloading techniques partition workloads and distribute tasks among multiple layers (local device, edge device, cloud servers) such that the performance and efficiency objectives are met.
The collaborative end-edge-cloud architecture provides execution choices such that each workload can be executed on the device, on the edge, on the cloud, or a combination of these layers. Each execution choice effects the performance and energy consumption of the user end device, based on the system parameters such as hardware capabilities, network conditions, and workload characteristics. A distributed end-edge-cloud system consists of the following layers: • application layer: provides user level access to a set of services to be delivered by computing nodes • platform layer: provides a set of capabilities to connect, monitor and control end/edge/cloud nodes in a network • network layer: provides connectivity for data and control transfer between different physical devices across multiple • hardware layer: provides hardware capabilities for computing nodes in the system Each layer presents a diverse set of requirements, constraints, and opportunities to tradeoff performance and efficiency that vary over time. For example, the application layer focuses on the user's perception of algorithmic correctness of services, while the platform layer focuses on improving system parameters such as energy drain and data volume migrated across nodes. Both application and platform layers have different measurable metrics and controllable parameters to expose different opportunities that can be exploited for meeting overall objectives. In the case of DL inference, different DL model structures present opportunities in the application layer, and different computation offloading decisions in a collaborative end-edge-cloud system present opportunities in the platform layer, both for optimizing the execution while meeting required model accuracy.

Intelligence for Orchestration
Runtime system dynamics affect orchestration strategies significantly in addition to requirements and opportunities. Sources of runtime variation across the system stack include workload of a specific computing node, connectivity and signal strength of the network, mobility and interaction of a given user, etc. Considering cross-layer requirements, opportunities, and runtime variations provide necessary feedback to make appropriate choices on system configurations such offloading policies. Identifying optimal orchestration considering the cross-layer opportunities and requirements in the face of varying system dynamics is a challenging problem. Making the optimal orchestration choice considering these varying dynamics is an NP-hard problem, while brute force search of a large configuration space is impractical for real-time applications. Understanding the requirements at each level of the system stack and translating them into measurable metrics enables appropriate orchestration decision making. Heuristic, rule-based, and closed-loop feedback control solutions are not efficient until reaching convergence, which requires long periods of time [39]. To address these limitations, reinforcement learning approaches have been adapted for the computation offloading problem [36]. Reinforcement learning builds specific models based on data collected over initial epochs, and dramatically improves the prediction accuracy [39].

MOTIVATION
This section presents a comprehensive investigation of DL inference for multi-users in end-edgecloud systems. We examine the scenario using a real setup including five AWS a1.medium instances with single ARM-core as end-node devices connected to an AWS a1.large instance as edge device and an AWS a1.xlarge instance as cloud node. We conduct experiments for DL inferences with the MobileNetV1 model while varying (i) network connection, (ii) number of active users, and (iii) accuracy requirement. We consider three possible execution choices: (i) on device, (ii) on edge, and (iii) on cloud. The device, edge, and cloud execution choices represent executing the inference completely on the local device, on the edge, and on the cloud respectively. The detailed specifications for the end-edge-cloud setup appear in Section 5.3.

Impact of System Dynamics on Inference Performance
Network. We consider two possible levels of network connections: (i) a low-latency (regular) network that has the signal strength for better connectivity, and (ii) a high-latency (weak) network that has a weaker signal with poor connectivity. Figure 1 (a) shows the response time of MobileNet application on user device, edge, and cloud layers with regular and weak networks. With a regular network, the response time is highest for executing the application on the user end device. The response time decreases as the computation is offloaded to edge and cloud layers, with the higher computational resources. With a weak network, the response time of the edge and cloud layers is higher, as the poor signal strength adds delay. The response time of the edge node in this case is higher than the cloud layer, given the lower compute capacity of the edge node. Performance of the user end device is independent of the network connection, resulting in lowest response time. This demonstrates the spectrum of response times achievable with compute nodes at different layers, under varying network constraints. For example, the best execution choice with a regular network is the cloud layer, whereas it is the local execution with a weak network.
Users. We examine user variability by considering multiple simultaneously active users ranging from 1 to 5. Figure 1 (b) shows the average response time with varying number of users. The average response time remains constant when running the application on a user end device, i.e., each user executes the application on their local device. When offloaded to the edge layer, the average response time increases significantly as the number of users increase. This is attributed to the increased network load with multiple simultaneously active users as well as limited resources at the edge layer to handle several user requests concurrently. The average response time also increases when offloaded to the cloud layer as the number of simultaneous users increases. However, the response time is lower when compared to the edge layer, since the cloud layer has a larger volume of resources to handle multiple simultaneous user requests.
Accuracy. We demonstrate the impact of varying DL models on performance under different system dynamics. We select between eight models with Top-5 accuracy between %72.8 and %89.9, while also considering all three layers for execution, and between 1 and 5 simultaneously active users. Figure 1 (c) shows the average response time achieved with varying levels of average accuracy  Figure 1 (c) represents a unique case of an execution choice (among device, edge, and cloud), number of active users (among 1 to 5), and accuracy level. We present the average response time achieved with different levels of accuracy. As expected, the response time increases with increase in model accuracy. However, we observe tradeoffs among different response times between accuracy and number of active users. For instance, it is possible to support multiple users within the response time of servicing a single user, by lowering the model accuracy.
Considering the three major sources of variations in number of users, network conditions, and model accuracy, finding an optimal choice of execution for end-edge-cloud architectures at runtime is challenging. As such architectures scale in the number of users and edge nodes, the accuracyperformance Pareto-space becomes increasingly cumbersome for finding an optimal configuration among the fine-grained choices. Brute force and smart search algorithms do not offer practically feasible solutions to orchestrate applications in real-time. While machine learning algorithms can identify near-optimal configuration choices, they require exhaustive training, considering continuously varying system dynamics. We propose to employ online reinforcement learning to understand the volatility of system dynamics and make near-optimal orchestration decisions in real-time to improve the response time of DL inferencing on end-edge-cloud architectures.

Related Work
We categorize research related to optimally deploying DL services at the edge in two ways: (i) work related to deploying DL inference tasks over the end-edge-cloud collaborative architecture, and (ii) work related to adopting reinforcement learning methods to optimally offload tasks.
DL Inference in End-edge-cloud Networks. Prior works propose frameworks to decompose DL inference into tasks and perform distributed computations. In these works, a DL model can be partitioned vertically or horizontally along the end-edge-cloud architecture. Generally, DL models are partitioned according to the compute cost of model layers and required bandwidth for each layer to be distributed among the end-edge-cloud [15,16,34,46]. These works find the optimal partition points based on traditional optimization techniques and offer design-time optimal solutions. Some efforts try to reduce the computation overhead of DL tasks through various model optimization methods such as quantization. These methods transform or re-design models to fit them into resource-constrained edge devices with little loss in accuracy [10,12,26]. AdaDeep [22] proposes a Deep Reinforcement Learning method to optimally select from a pool of compressed models according to available resources. However, AdaDeep relies only on the model selection technique while our work combines computation offloading and model selection techniques to achieve the optimal response time.
Learning-based Offloading. Prior works address the offloading problem to optimize different objectives including latency and energy consumption. Most of the works formulate the offloading problem with limited number of influential parameters and adopt online learning techniques with numerical evaluation [1, 6-8, 17, 20, 27, 33, 43, 45]. Lu et. al. [24] propose a Deep Recurrent Q-Learning algorithm based on Long Short Term Memory network to minimize the latency for multi-service nodes in large-scale heterogeneous MEC and multi-dependence in mobile tasks. The algorithm is evaluated in iFogSim simulator with Google Cluster Trace. [36] proposes a Q-Learning based algorithm to minimize energy by considering various parameters in task characteristics and resource availability. Young Geun et al. [19] propose a reinforcement learning based offloading technique for energy efficient deep learning inference in the edge-cloud architecture. The work focuses on the learning for heterogeneous systems and lacks a comprehensive solution for multiusers end-edge-cloud systems. Haung et al. [14] uses a supervised learning algorithm for complicated radio situations and communication analysis and prediction to make an optimal actions to obtain a high quality of service (QoS). However, our proposed work employs model-free reinforcement learning algorithm to find the optimal orchestration scheme. There have been other efforts which apply game theory algorithms to address the orchestration problem in the network. Apostolopoulos et al. [2] propose a decentralized risk-aware data offloading framework using non-cooperative game formulation. The work uses a model-based game theory algorithm to find the optimal offloading decision which makes difference with our proposed model-free reinforcement learning approach. Model-based algorithm use a predictive internal model of the system to seek outcomes while avoiding the consequence of trial-and-error in real-time. The approach is sensitive to model bias and suffers from model errors between the predicted and actual behavior leading to sub-optimal orchestration decisions. Our Model-free RL technique operates with no assumptions about the system's dynamic or consequences of actions required to learn a policy.
Some works have been applied traditional optimization techniques to optimize the computation offloading problem [5]. Yuan et al. [48] model a profit-maximized collaborative computation offloading and resource allocation algorithm to maximize the profit of systems and meet the required response time. In another work, Bi et al. [4] propose a partial computation offloading method to minimize the total energy consumed by mobile devices. The work formulates the problem and optimizes using a novel hybrid meta-heuristic algorithm. Considering systems are unknown with dynamic behavior, the traditional optimization techniques are not applicable for runtime decisionmaking. Table 1 positions our work with respect to state-of-the-art solutions. Our solution uses RL to optimally orchestrate DL inference in multi-user networks considering offloading and DL model selection techniques combined together.

Contributions
The ideal DL inference deployment provides maximum inference accuracy and minimum response time. Figure 2 shows an abstract overview of our target multi-layered architecture for online computation offloading of DL services. We consider three layers viz., user-end device, edge and cloud. Further, we classify this architecture into virtual system layers that include application, platform, network and hardware layers. Each of the virtual system layers provide sensory inputs for monitoring system and application dynamics such as DL model parameters, accuracy requirements, availability of devices for execution, network characteristics, and hardware capabilities. The Decision Intelligence component in Figure 2 periodically monitors resource availability from all virtual system layers to determine appropriate execution choice and DL models to achieve the required QoS (e.g, accuracy, response time). Decision Intelligence analyzes the system parameters to make orchestration decisions in terms of model selection, accuracy configuration, and offloading choices. The orchestrator is a software component that is hosted at the cloud layer and enforces the orchestration decisions upon receiving a service request from the user-end devices. Finding an optimal computation policy including offloading and model selection to optimize objectives (e.g., accuracy, response time) is considered an NP-hard problem. The problem generally can be solved using traditional optimization techniques such as heuristic-based methods, metaheuristic methods, or exact solutions. Considering systems are unknown with dynamic behavior, the traditional optimization techniques are not applicable for runtime decision-making to optimize objectives. Modeling an unexplored high-dimensional system is feasible using model-free reinforcement learning techniques [39]. Model-free RL operates with no assumptions about the system's dynamic or consequences of actions required to learn a policy. Model-free RL builds the policy model based on data collected through trial-and-error learning over epochs [39]. In this work, we use model-free reinforcement learning to deploy DL inference at the edge by considering offloading and model selection. Some works have been proposed to address the computation offloading problem using online techniques [1, 6-8, 17, 19, 27, 33, 43, 45]. However, there is no relevant work to investigate the integration of online learning with DL inference deployment. Therefore, the literature suffers from some shortcomings that are summarized as follows: • Cross-layer Optimization: online solutions have not previously coordinated offloading and model optimizations together. As Table 1 shows, all related work relies on only computation offloading (CO). To the best of our knowledge, for the first time, this paper considers both computation offloading and application-level adjustment (APP) together in order to achieve required QoS. • Real System Evaluation: most RL-based solutions in the literature are numerically evaluated.
Some works have been proposed and evaluated with simulators. As Table 1 shows, the literature lacks a real hardware implementation for online learning framework. This paper implements the online system on real hardware devices which leads to realistic evaluation of online agent's overhead. • End-to-End Solution: end-to-end solution considers a service from the moment a request is issued from the end-node device to delivering results to itself. Table 1 illustrates that the literature lacks an end-to-end solution.

ONLINE LEARNING FRAMEWORK
Our goal is to make offloading decisions and inference model selections in order to minimize inference latency while achieving acceptable accuracy. To do so, we first define the optimization problem, then we propose a reinforcement learning agent to solve the problem. Table 2 defines the notation used for the problem definition.

System Model and Problem Formulation
All computing devices in the end-edge-cloud system are represented by (S,E,C) where = { 1 , 2 , .., } represents a set of end-node devices whose number is ; represents the edge layer (in our case, a single device); C represents the cloud layer. Each end-node device requires a DL inference periodically. The inference model is selected from a pool of optimized models where each model has different characteristics including computational complexity and model accuracy. All device resources are represented in a tuple { , , } where represents processor utilization of device ; represents available memory for device ; represents network's connection condition between the device and upper layer's node.
The computation offloading decision determines whether each end-node device should offload an inference to higher-layer computing resources, or perform computation locally. The offload decision for each end-node device is represented by a tuple = { , , } where represents offloading decision to layer . If end-node device executes at layer ∈ { , , }, then = 1; otherwise it must be zero. For a given end-node device , the sum of all offloading decisions { , , } must equal 1. = { 1 , 2 , ..., } represents the offloading decision vector for all end-node devices. The inference model selection determines the implementation of the model deployed for each inference on each end-node device. Each end-node device can perform inference with one of DL models In general, response time is the total time between making a request to a service and receiving the result [31]. In our case, response time is the sum of the round trip transmission time from an end-node device to the node that performs the computation, plus the computation time. Response time for a request from end-node device with offload decision tuple = { , , } can be summarized as follows: Our objective is to minimize the average response time while satisfying the average accuracy constraint. The problem is formulated in the following formula: where is the spatial average accuracy for simultaneous DL inferences.

Reinforcement Learning Agent
Reinforcement learning (RL) is widely used to automate intelligent decision making based on experience. Information collected over time is processed to formulate a policy which is based on a set of rules. Each rule consists three major components viz., (a) state, (b) action, and (c) reward. Among the various RL algorithms [39], Q-learning has low execution overhead, which makes it a good candidate for runtime invocation. However, it is ineffective for large space problems. There are two main problems with Q-learning for large space problems [28]: (a) required memory to save and update the Q-Values increases as the number of actions and state increases. (b) required time to populate the table with accurate estimates is impractical for the large Q-table. In our case, increasing number of users will increase the problem's space dimension. The reason is more number of users leads to more number of rows and columns in the Q-table. Therefore, it takes more time to explore every state and update the Q-values. Due to the curse of dimensionality, function approximation is more appealing [28]. The Deep Q-Learning (DQL) algorithm combines the Q-Learning algorithm with deep neural networks. DQL uses Neural Network architecture to estimate the Q-function by replacing the need for a table to store the Q-values. In this work, we build an RL agent using two reinforcement learning algorithms: (a) an epsilon-greedy Q-Learning and (b) a Deep Q-Learning algorithms. We evaluate the RL agent with the mentioned algorithms considering different problem complexities. Figure 3 depicts high-level black diagram for our agent. The RL agent is invoked at runtime for intelligent orchestration decisions. In general, the agent is composed as follows: State Space: Our state vector is composed of CPU utilization, available memory, and bandwidth per each computing resource. Table 3 shows the discrete values for each component of the state. The state vector at time step is defined as follows: Action Space: The action vector consists of which inference model to deploy, and which layer to assign the inference. We limit the edge and cloud devices to always use the high accuracy inference model, and the end-node devices have a choice of different models. Therefore, the action space is defined as = { , } where ∈ { , , } and ∈ { 1 , 2 , ..., }.
To apply the accuracy constraint, the minimum possible reward is assigned when the accuracy threshold is violated. On the other hand, when the selected action satisfies the average accuracy constraint, the reward is negative average response time.  Choose action +1 with the largest ( +1 , +1 ) 13: To Updating Qtable: 14: ← +1 15: end while 4-8: Next, either the state-action pair ( , ) with the highest -value is identified to choose the next action to take, or a random action is selected with probability . 9-10: The selected action is applied and normal execution resumes. After all inferences are completed, the reward for the execution period is calculated based on measured response time. 11-12: Based on the resource monitors, the new state +1 is identified, along with the stateaction pair with highest Q-value. 13: The Q-value of the previous state-action pair is updated. 14: The current state is updated, and the loop continues.

Deep Q-Learning
Algorithm. Q-Learning has been applied to solve many real-world problems. However, it is unable to solve high-dimensional problems with many inputs and outputs [28] as it is impractical to represent the Q-function as a Q-table for large pair of and . In addition, it is unable to transverse ( , ) pairs. Therefore, a neural network is used to estimate the Q-values. The Deep Q-learning Network (DQN) inputs include current state and possible action, and outputs the corresponding Q-value of the given action input. The neural network approximation is capable of handling high dimensional space problems [44]. One of the main problems with Deep Q-Learning is stability [28]. In order to reduce the instability caused by training on correlated sequential data, we improve the DQL algorithm with replay buffer technique [21]. During the training, we calculate the loss and its gradient using a mini-batch from the buffer. Every time the agent takes a step (moves to the next state after choosing an action), we push a record into the buffer. Algorithm 2 defines Deep Q-Learning algorithm which is described below: Line Description 4: First the agent determines the current system state from the resource monitors.

4:9
Next, either the state-action pair , with the highest Q-value estimated by neural network ( ) is identified to choose the next action to take, or a random action is selected with probability . 10:11 The selected action is applied and normal execution resumes. After all inferences are completed, the reward for the execution period is calculated based on measured response time. 12: At each time step, each record ( , , , +1 ) is added to a circular buffer called the replay buffer.

13:
We randomly sample Batch Size records from the buffer and then feed it to the network as mini-batch. 14: We calculate the temporal difference loss on the mini-batch and perform a gradient descent calculation to update the network. The temporal difference loss function calculates the mean-square error of the predicted and target Q-values as the loss of the mini-batch.

15:
The current state is updated, and the loop continues. There is few study about the theoretical analysis of the computational complexity of reinforcement learning because of the problem itself that reinforcement learning solves is hard to be explicitly modeled. Reinforcement learning is in the nature of trail-and-error and exploration-and-exploitation, which involves randomness and makes it difficult to be theoretically analyzed. The complexity of problem for Bruteforce strategy is discussed in the following: Brute-force strategy searches the entire State×Action space of the problem and sort corresponding Q-values in order to find out the optimal action. Therefore, we can define the state space complexity as follows:  (1) Request (2) Request Orchestration (3) Decision (4) Decision (4) Update (5) Update ( where, stands for the number of end-devices. , , and represent the number of CPU, Memory, and Network condition levels for end devices, respectively. In addition, ′ , ′ , and ′ represent the number of CPU, Memory, and Network condition levels for edge and cloud devices, respectively. Besides, the action space is defined as ( ) . Therefore, the complexity is defined as follows: The reinforcement learning agent requires distinct state-action pairs for training the Deep Qnetwork. To generate distinct state-action pair vectors, our proposed framework supports execution requests that are submitted by all the end-devices synchronously. With synchronous requests, we eliminate the discrepancy of different optimal actions for the same state vector.

FRAMEWORK SETUP
In this section we describe our proposed framework for dynamic computation offloading based on online learning, targeted at multi-layered end-edge-cloud architecture. Figure 4 shows our proposed framework for end-edge-cloud architecture, integrating service requests, resource monitoring, and intelligent orchestration. The Intelligent Orchestrator (IO) acts as an RL-agent for making computation offloading and model selection decisions. The end-device layer consists of multiple user-end devices. Each end-device has two software components: (i) Intelligent Service -an image classification kernel with DL models of varying compute intensity and prediction accuracy; (ii) Resource Monitoring -a periodic service that collects devices' system parameters including CPU and memory utilization, and network condition, and broadcasts the information to the edge and cloud layers. Both the edge and cloud layers also have the Intelligent Service and Resource Monitoring components. The Intelligent Orchestrator acts a centralized RL-agent that is hosted at the cloud layer for inference orchestration. The agent collects resource information (e.g., processor utilization, available memory, available bandwidth) from Resource Monitoring components throughout the network. The agent also gathers the reward information (i.e., response time) from the environment in order to learn an optimal policy. The agent builds the Q-function based on the RL algorithm. It builds a Q-Table for Q-Learning algorithm and a Q-Network for Deep Q-Learning algorithm based on cumulative reward obtained from the environment over time. Quality of Service Goal provides the required QoS for the system (i.e., the accuracy constraint). Figure 4 illustrates the procedure step-wise of the inference service in our framework. The end-device layer consists of resource-constrained devices that periodically make requests to a DL inference service (step 1). The requests are passed through the edge layer (step 2) to the cloud device to be processed by Intelligent Orchestrator (step 3). The agent determines where the computation should be executed, and delivers the Decision to the network (step 4). Each device updates the agent after it performs an inference with the response time information of the requested service (step 5). In addition, all devices in the framework send the available resource information including the processor utilization, available memory, and network condition to the cloud device (step 5).

Benchmarks and Scenarios
MobileNets are small, low-latency deep learning models trained for efficient execution of image classification on resource-constrained devices [13]. For DL workloads, we consider MobileNetV1 image classification application as the benchmark [13]. We deploy the MobileNetV1 service for end-node classification. We consider eight different MobileNet models ( 0 through 7) with varying levels of accuracy and performance. Each model among 0 through 7 has varying number of Multiply-Accumulate units (MACs), MAC width and data format (e.g., FP32 and Int8), exposing models with different accuracy-performance trade-offs. Table 4 summarizes the MobileNet models we consider, detailing the number of Multiply-Accumulates (MACs), MAC width and data formats (e.g., FP32 and Int8). The multiplier width is used to reduce a network's size uniformly at each layer. For a given layer and multiplier width, the number of input channels and the number of output channels is decreased and increased, respectively, by a factor of the width multiplier. During the orchestration phase, we select an appropriate model from 0-7 to achieve the target level of classification accuracy while maximizing the performance.
Our framework supports multiple end-devices, networked with edge and cloud layers. For evaluation purposes, we set the maximum number of simultaneously active user devices to five. Each user-end device is connected to a single edge device, and can request a DL inference service to the cloud layer. The cloud layer hosts the IO that contains the RL agent, which handles the inference service requests. Upon on each service request, the RL agent is invoked to determine: (i) where the request should be processed and (ii) what DL model should be executed for the corresponding request. The RL agent's goal is to minimize average response time for all end-node devices while satisfying the accuracy constraint. This enforces quality control by imposing a strict threshold on the average DL model accuracy. In this work, we conduct experiments under four unique scenarios with varying network conditions. Each scenario represents a combination of regular (R) and weak (W) network signal strength over five user-end devices (S1-S5) and 1 edge device (E). The experimental scenarios are summarized in Table 5. The regular network has no transmission delay, while we add 20ms delay to all outgoing packets to emulate the weak connection behavior.
Each experimental scenario in Table 5 shows the network condition of the specific device. Putting together the five different user devices and one edge device forms a unique combination of varying network conditions per each experimental scenario.

Experimental Setup
The platform consists of five AWS a1.medium instances with single ARM-core as end-devices connected to an AWS a1.large instance as edge device and an AWS a1.xlarge instance as cloud node. Table 6 summarizes device specifications in details. DL model inferences are executed on processor cores on all nodes using ARM-NN SDK [23]. The inference engine is a set of open-source Linux software tools that enables machine learning workloads on ARM-core-based devices. The framework's message passing protocol is implemented using web services deployed at each node. Section 7.2 provides our analysis on framework's setup overhead.

Hyper-parameters and RL Training
An RL agent has a number of hyper-parameters that impact its effectiveness (e.g., learning rate, epsilon, discount factor, and decay rate). The ideal values of parameters depend on the problem complexity, which in our case scales with the number of users (i.e., active end-node devices). In order to determine the learning rate and discount factor, we evaluated values between 0 and 1 for each hyper-parameters. We observed that a higher learning rate converges faster to the optimal, meaning the more the reward is reflected to the Q-values, better the agent works. We also observed that a lower discount factor is better. This means that the consecutive actions have a weak relationship, so that giving less weight to the rewards in the near future improves the convergence time. Table 7 shows the different problem configurations we used to determine the hyper-parameters. We train the agent with two different learning algorithms (See Section 4.2). Our Q-Learning agent initializes a Q-table with Q-values of zero, and chooses actions using an − policy where is the exploration rate. We initially set = 1, meaning the agent selects a random action with probability 1, otherwise it selects an action that gives the maximum future reward (i.e., Q-value) in the given state. Although we perform probabilistic exploration continuously, we decay the exploration by epsilon decay parameter (See Table 7) per agent invocation. The Deep Q-Learning agent uses different neural network structure for different number of users as the problem complexity changes.
We train DNN models with two fully connected layers where the hidden layers have 48, 64, 128 neurons for three, four, and five devices, respectively. We implement the experience replay as a FIFO buffer with size equal to 1000. In order to update the network, at each step, we randomly sample 64 records from the buffer and then use them as a mini-batch. We use − policy to train the Deep Q-network, where we initially set the equal to 1.

EVALUATION RESULTS AND ANALYSIS
In this section, we demonstrate the effectiveness of our online learning based inference orchestration. We evaluate our approach on the multi-layered end-edge-cloud framework, described in Section 4. Our approach features online reinforcement learning for intelligent orchestration, DL inference services and end-edge-cloud architectures, targeting DL inference performance. [36] presents state-of-the-art machine learning based orchestration for end-edge-cloud architecture baseline. For a fair comparison, we evaluate our approach against the strategy proposed in [36], which integrates the aforementioned features of our approach.

Performance Analysis
We evaluate our agent's ability to identify the optimal orchestration decision at each invocation. Through reinforcement learning, the agent predicts orchestration decisions including offloading policy and DL model configuration to maximize performance and meet the accuracy threshold. At design time, we determine the true optimal configuration in any given conditions of workloads, network, and number of active users using a brute force search. First, we compare our reinforcement learning based Intelligent Orchestrator's (IO) prediction accuracy against this true optimal configuration. Our proposed approach with both Q-Learning and Deep Q-Learning algorithm has yielded a 100% prediction accuracy in comparison with the true optimal configuration. Thus, our reinforcement learning based orchestration decisions always converge with the optimal solution. Next, we evaluate our agent's efficacy by comparing it with a representative state-of-the-art [36] baseline in terms of performance and accuracy. To implement the baseline policy into our framework, we limit the agent to actions that specify offloading decisions = { }, using the most accurate DL model. We additionally compare fixed orchestrations for points of reference. The fixed solution is limited to configurations where all end-devices either (a) perform the most accurate DL inference execution locally, (b) offload to the edge, or (c) offload to the cloud. In the following subsections, we demonstrate the efficacy of our proposed agent to find the optimal configuration in presence of different number of users (up to five). Then, we investigate its ability to adapt to network variations and evaluate its overhead. We explain the impact of varying DL models on the performance under different system dynamics and elaborate how the proposed agent follows the defined constraints.  6.1.1 User Variability. To evaluate the user variability, we consider up to five simultaneously active user-end devices, keeping the network constraints constant. We consider five different levels of accuracy thresholds viz., Min, 80%, 85%, 89%, and Max. Min refers to the accuracy threshold for computing where no constraint is applied to the learning algorithms (See Equation 4) and Max represents the accuracy threshold for computing where the average accuracy constraint is set to 89.9%. We present the average response time and average accuracy for each of these thresholds using our proposed approach. For evaluation, we also present the average response time and accuracy metrics achieved with the state-of-the-art baseline approach [36], and three fixed orchestration decisions viz., device only, edge only and cloud only. Fixed Strategies Figure 5 shows the average response time and accuracy for different numbers of active users for regular network conditions (represented by scenario Exp-A in Table 5), using different orchestration strategies. The x-axis represents the number of active users. Each bar represents a different orchestration decision made by using the corresponding orchestration strategy. With the device only strategy, each user-end device executes the inference service on the local device. Thus, varying number of users has no effect on the average response time in this case. With the edge and cloud only strategies, simultaneous requests contend for edge and cloud resources. This increases the average response time significantly, as the number of users increase. For instance, the fixed edge only strategy with five active users leads to an average response time of 1140ms, while it is 665 with cloud only strategy. Higher volume of available resources at the cloud layer results in relatively better average response time in comparison with the edge only strategy. On the other hand, the average response time with the device only strategy is 459 , representing the optimal case. Baseline With the SOTA [36] approach, the average response time remains constant until the number of users is two. This is due to the orchestration decision of distributing the services across edge and cloud layers. As the number of users increase to three, the service requests contend for resources, leading to an increase in the average response time. With the number of users increasing from three through five, the average response time increases, but at a relatively lower rate, exhibiting efficient utilization of the edge and cloud resources. As the number of users increase, the efficiency of the baseline approach over the fixed strategies is more prominent. Both the baseline and fixed strategies are agnostic to model selection and configuration, retaining the maximum prediction accuracy of the inference service. Thus the average accuracy remains constant with the aforementioned strategies, as shown in Figure 5. Our proposed solution Our proposed solution achieves the same average response time in comparison with the baseline for the Max accuracy scenario. When the accuracy threshold is relaxed, our reinforcement learning based intelligent orchestrator selects appropriate models (among 0-7) to improve the average response time. As the number of users increase, our solution leverages the model selection combined with offloading technique to address the potential increase in response time. With appropriate model selection, our approach reduces the compute intensity, and consequently maintains a lower average response time even with the increasing number of users. Trivially, the average response time with our approach is lower as the accuracy threshold is reduced. However, it should be noted that we enforce the boundaries on tolerable loss of accuracy with our model selection decisions. Figure 5 shows the average response time and average accuracy with our solution over different scenarios of accuracy thresholds and varying number of users. Our solution provides up to 35% improvement in the average response time in comparison with the baseline, within a tolerable loss of 0.9% accuracy. Table 8 shows the orchestration decisions of our agent for different numbers of active users, and also over four different experimental scenarios (Table 5). We present the orchestration decision and the average response time achieved with each decision, for the maximum accuracy threshold scenario.
6.1.2 Network variation. We consider two possible levels of network connection: (i) a regular network that has low latency, and (ii) a weak network that has high latency. We add 20ms delay to all outgoing packets to emulate the weak connection behavior. With varying network conditions, there is an increased delay with offloading decisions across the network. Both the baseline and fixed approaches are affected by the weak network conditions, resulting in a higher average response time. The fixed strategies employ the trivial device, edge and cloud only offloading decisions, suffering higher latency. The baseline approach is confined to only an intelligent offloading strategy, which also results in higher average response time inevitably. On the other hand, our proposed solution adapts to varying network conditions by opportunistically exploiting the accuracy tradeoffs through model selection. This way, we address for the latency penalty levied by weak network conditions by reducing the compute intensity of the workloads, within the tolerable accuracy bounds. Table 9 shows the orchestration decisions made by our intelligent orchestrator, average response time, and average accuracy achieved over varying networking conditions. Each experiment scenario (Exp-A through Exp-D) combines different network conditions for each node in the network (See Table 5). For example, in Exp-A, all the nodes are connected with regular network, whereas in Exp-B, nodes 1, 3, and 5 have regular connections and the rest have weak connections. We set the number of active users to five. Model Selection Within each experiment scenario, the average response is lower as the accuracy   threshold is relaxed. 0 through 7 represent models with different response time and accuracy levels. For instance, models 0, 4, 2, 7 and 7 are selected respectively for accuracy thresholds ranging from Max through Min in Exp-A. Our proposed orchestrator explores the Pareto-optimal space of model selection and offloading choice, combining the opportunities at application and platform layers simultaneously. For instance in Exp-A, maintaining an accuracy level of 89% results in an average response time of 269.8ms, by i) setting the models to 4, 4, 4, 0, and 4 on devices S1-S5, and ii) device configurations to L (local device), L, L, E (edge) and L for S1-S5. However, the average response time can be improved by sacrificing the accuracy within a pre-determined tolerable level. For instance, by lowering the accuracy threshold by 4% (from 89% to 85%), the average response time can be reduced by 88% (from 269ms to 143ms) by i) setting the models to 2, 6, 5, 6, and 5 on devices S1-S5, and ii) device configurations to L (local device), L, L, L and L for S1-S5. With varying network conditions, our solution explores the offloading and model selection Pareto-optimal space at run-time to predict the optimal orchestration decisions.
For example, in Exp-D, our framework obtains 356.75ms on average response time with significantly weak network connectivity, while it can adapt to regular connectivity in Exp-A to obtain 269.80ms on average response time. In this case, the average accuracy is 89.1% which shows 0.8% error with the maximum average accuracy. The baseline [36] orchestrates the most accurate DL Table 9. Results of the proposed framework for different accuracy constraints for different experiments (five users). For example, in Exp-D with 89% average accuracy constraint, our framework orchestrates 1, 2, 3, and 4 to execute DL inference using model 4 locally and offload inference execution using model 0 at the cloud. However, the baseline obtains the maximum accuracy by executing the most accurate DL inference locally for 1, 4, and 5 while offloading 0 to the edge and cloud for 3 and 2, respectively. inference execution to obtain 506.62ms and 418.9ms average response time in Exp-D and Exp-A, respectively. Orchestration decisions of the baseline approach over different experimental scenarios is summarized in Table 10. Although our proposed framework and the baseline can adapt to network variability, our agent provides additional trade-off opportunities to deploy different models combined with offloading technique. This leads to up to 35% speedup while sacrificing less than 1% average accuracy.   .

Overhead Analysis
Developing a global RL agent for optimal runtime orchestration decisions in an end-edge-cloud system incurs overhead to multiple sources. We evaluate the sources of overhead in both exploration and exploitation phases to demonstrate the feasibility of our proposed solution.
6.2.1 Exploration Overhead. We evaluate the time required by the proposed agent for the training phase to identify an optimal policy. Figure 6 shows the training phase for different numbers of end-devices under different accuracy constraints. We train the agent with Q-Learning and Deep Q-Learning algorithms under different accuracy constraints (See Figure 6.(a) and 6.(b), respectively). The convergence time for five devices with different policies are summarized in Table 11. Q-Learning agent converges faster than Deep Q-Learning agent for the three End-devices scenario. However, increasing the number of End-devices leads to the more complex problem. Deep Q-Learning agent converges up to 17.5× faster than Q-Learning agent for the five End-devices scenario. In other words, Deep Q-Learning algorithm converges faster for high-dimensional space problems. Furthermore, SOTA converges faster since the agent only uses limited actions (3 actions for computation offloading) making a low-dimensional space problem. In addition, we observe that the training phase can be accelerated by exploiting previous experiences in similar scenarios known as transfer learning strategy. Figure 7 shows that the strategy can alleviate the convergence up to 12.5× and 3.3× for Q-Learning and Deep Q-Learning algorithms, respectively. In the transfer learning strategy, we train a model with minimum accuracy threshold from scratch. Then, we initialize model with the trained model to reduce the convergence time. In conclusion, the Deep Q-Learning algorithm with the transfer learning strategy can speedup the convergence time up to 57.7× in comparison with Q-Learning algorithm for the five End-devices scenario.
6.2.2 Run-time Overhead. The agent is invoked periodically at runtime, imposing overhead on DL inference execution. We evaluate the following components individually: (a) Resource Monitoring: A continuous resource monitoring service imposes runtime overhead in terms of DL inference response time. Figure 8 shows that the latency overhead for all layers is negligible (less than 0.8% of minimum response time overall). (b) Message Broadcasting: Sharing resource usage and orchestration decision information over the network potentially increases DL inference response time. Table 3 shows the additional network latency for different network conditions. The request is the latency required to send an input image to a higher layer, and dominates the sources of network overhead. We observe that the broadcasting, in total, does not impose more than 2% of overall response time.
(c) Intelligent Orchestrator: The Q-Learning agent's logic itself takes on average 0.6ms to execute in the cloud. While, the Deep Q-Learning agent's step takes 11 on average to execute using NVIDIA RTX 5000 in cloud. During exploitation, our trained agent identifies the optimal orchestration decision within five invocations. We conclude that after an agent is trained, the improvements of 35% in average response time compared to prior art justifies the total overhead of our agent.

CONCLUSION
Cross-layer optimization that considers both model optimization and computation offloading together provides an opportunity to enhance performance while satisfying accuracy requirements. In this paper, for the first time, we proposed an online learning framework for DL inference in end-edge-cloud systems by coordinating tradeoffs synergistically at both the application and system layers. The proposed reinforcement learning-based online learning framework adopts model optimization techniques with computation offloading to find the minimum average response time for DL inference services while meeting an accuracy constraint. Using this method, we observed up to 35% speedup for average response time while sacrificing less than %0.9 accuracy on a real end-edge-cloud system when compared to prior art. Our approach shows that online learning can be deployed effectively for orchestrating DL inference in end-edge-cloud systems, and opens the door for further research in online learning for this important and growing area.


extfieldsofstudy:
Computer Science
Mathematics

text:
Provably Efficient Kernelized Q-Learning

We propose and analyze a kernelized version of Q-learning. Although a kernel space is typically infinite-dimensional, extensive study has shown that generalization is only affected by the effective dimension of the data. We incorporate such ideas into the Q-learning framework and derive regret bounds for arbitrary kernels. In particular, we provide concrete bounds for linear kernels and Gaussian RBF kernels; notably, the latter bound looks almost identical to the former, only that the actual dimension is replaced by a different notion of dimensionality. Finally, we test our algorithm on a suite of classic control tasks; remarkably, under the Gaussian RBF kernel, it achieves reasonably good performance after only 1000 environmental steps, while its neural network counterpart, deep Q-learning, still struggles.

1 Introduction Q-learning, which dates back to as early as Watkins and Dayan (1992), has undergone tremendous development in the past decades and remains one of the most sample-efficient reinforcement learning (RL) frameworks in practice. The modern implementation of Q-learning maintains a value function Q t at each step t such that where (s, a, r, s ′ ), representing the quadruple of state, action, reward, next state, is sampled from historical data, γ is a discounting factor, and actions that maximizes Q t are taken with priority (Mnih et al., 2013). The most successful implementation of the above paradigm is perhaps deep Q-learning (DQN) (Mnih et al., 2013), in which each Q t is represented by a (deep) neural network and actions are taken to maximize Q t with probability 1 − ǫ, and randomly otherwise. Despite the success of DQN, our theoretical understanding of Q-learning is still lacking. While there exist regret analyses for certain versions of tabular Q-learning (Jin et al., 2018;Liu and Su, 2021), these algorithms and their analyses hardly generalize to non-tabular settings. Algorithms and corresponding regret analyses have also been derived for more general function classes (see e.g. ; Zhou et al. (2021b), among others). However, the proposed algorithms use either episodic value iteration , which is not sample-efficient in practice, or extended value iteration Zhou et al. (2021b), which is not time-efficient in practice.
We seek to fill the gap between theory and practice in this paper. Specifically, we propose and analyze a kernelized version of (1), named kernelized Q-learning (KQL), where each Q t is restricted to a reproducing kernel Hilbert space (RKHS) and optimized with kernel ridge regression, and exploration is done through upper confidence bound.
RKHS are non-parametric function classes that are rich enough in that they are dense in the space of continuous functions if the kernel is universal (Sriperumbudur et al., 2011). Therefore, RKHS are, in some sense, as universal as neural networks (Hornik et al., 1989) while being easier to analyze thanks to decades of research on kernel machines. Combining standard machinery for analyzing kernel-based learning with our novel approach to analyze Q-learning, we arrive at general regret bounds for arbitrary kernels (Theorem 6.1); in particular, we provide concrete regret bounds for linear kernels (Corollary 6.2) and Gaussian RBF kernels (Corollary 6.4). Notably, the latter looks almost identical to the former, only that the actual dimension is replaced by a different dimensionality that is at most polylogarithmic in the number of steps.
We complement our theoretical analyses with experiments on a subset of classic control tasks provided in OpenAI Gym (Brockman et al., 2016). We faithfully implement the exact KQL algorithm for which we derive regret bounds and choose hyperparameters based on the bounds. We demonstrate superior sample efficiency of KQL, even when compared with DQN. To the best of our knowledge, KQL is the first provably low-regret algorithm that excels in commonly used benchmarks.  (2019); Zhang et al. (2020; gave regret bounds in the episodic setting. Regret bounds for the discounted setting was not studied until recently (Liu and Su, 2021;He et al., 2021b), due to trickier definition of the regret.
Later work generalizes tabular analyses to the linear model episodic setting Zanette et al., 2020), the linear mixture model episodic setting (Cai et al., 2020;Ayoub et al., 2020;Modi et al., 2020;Zhou et al., 2021a;He et al., 2021a), and the linear mixture model discounted setting (Zhou et al., 2021b). We note here that the linear mixture model assumes the model class has finite (and small) degrees of freedom, which mitigates many challenges in model estimation (see discussion in Jin et al. (2020, Related Work)). In particular, while Zhou et al. (2021b) gives a seemingly better regret bound than ours when the model class is linear in certain sense, they are under far stricter assumptions.
This paper is most related to , which proposes and analyzes KOVI, a kernelized version of episodic value iteration. The major difference is that  operates on an episodic setting, where in each episode, an optimistically optimal Q-value function is calculated based on all the historical data using episodic value iteration. On the other hand, we focus on the non-episodic setting, where in each step, a new Q-value function, which is not necessarily (optimistically) optimal based on current historical data, is calculated from the Q-value function from the previous step using one-step discounting. Such difference indeed affects theoretical analysis in that the non-episodic update introduces pathological dependencies that must be properly handled (e.g., Lemma 3.12). Furthermore, it also makes our algorithm significantly more applicable to real-world problems. For example, in our MountainCar experiment (Section 7), the length of an episode is 200. Given a budget of 1000 interactions, KOVI can only update its value functions 1000/200 − 1 = 4 times (since each step in an episode uses a different value function). It is very unlikely that any progress can be made after such a small number of parameter updates (indeed, we were not able to make KOVI work on Mountain-Car after extensive parameter tuning or even hacking). On the other hand, KQL does not distinguish between different episodes, and can update its value function 999 times. In fact, we will show that KQL even outperforms DQN in the low-budget setting.
Other kernelization efforts include Xu et al. (2005), which uses kernel regression to approximate the discounted return of a Markov chain, Xu et al. (2007), which uses kernel regression as a subroutine in a policy iteration procedure, no exploration is involved thus no regret bound can be obtained; Chowdhury and Gopalan (2019), which requires very restrictive assumptions, as discussed in ; , which assumes linear mixture models, therefore suffers from aforementioned limitations of such models; Ormoneit and Sen (2002); Barreto et al. (2016), which are based on local averaging and require Lipschitzness assumptions, and no exploration is involved thus no regret bound can be obtained; Domingues et al. (2021), which is similarly based on local averaging and require Lipschitzness assumption, but with Lipschitzness-based exploration. More general function approximation classes have also been considered. Notably, ; Ayoub et al. (2020) gave regret bounds in terms of Eluder dimension and covering number of the function class. However, most of these attempts either result in generally intractable algorithms (Krishnamurthy et al., 2016;Jiang et al., 2017;Dann et al., 2018;Dong et al., 2020;Ayoub et al., 2020), or make very restrictive assumptions such as deterministic environment (Wen and Van Roy, 2013;, or the existence of a finite latent state space .

Bandits
Bandit problems can be thought as a special case of RL problems by setting the horizon to 1 in the episodic setting, or setting the discounting factor to 0 in the discounted setting. Naturally, many ideas for RL analyses originates from the bandit literature.
Analyses for RL is generally much harder than for bandits, in that it needs to additionally avoid exponential dependencies on the state space and horizon. In particular, (near) optimal dependencies for these quantities require very sophisticated techniques.

Preliminaries
For a measurable space X, let B(X) be the space of real-valued bounded measurable functions over X equipped with the supremum norm · ∞ , let P(X) be the set of all probability measures over X. For any positive integer n, denote by [n] the set {1, 2, · · · , n}. For any two functions f, g : X → [0, ∞), f (x) = O(g) means that there exists c ≥ 0 such that for any x ∈ X, f (x) ≤ c · g(x).
Let H be a Hilbert space. Denote by ·, · H the inner product on H. Denote by · H the norm induced by the inner product. If T : H → H is a bounded self-adjoint positive-definite linear operator, define the Mahalanobis norm f T = T f, f H . Denote by B HS (H) the space of Hilbert-Schmidt operators from H to H. Denote by ·, · HS the inner product on B HS (H). Denote by · HS the norm induced by the inner product. For any u, v ∈ H, denote by u ⊗ v the linear operator such that for any f ∈ H, Let H be a real-valued RKHS over a set X such that the corresponding kernel K is bounded. For any x ∈ X, denote by K x the reproducing function at x, i.e., K x is the unique function that satisfies for any . For any f ∈ H, define the norm For any bounded linear operator T : H → H, define the norm

Effective Dimension and Pseudo Dimension
We are going to introduce two concepts used in the learning literature to capture the properties of a RKHS, effective dimension and pseudo dimension. Note that many similar concepts have been introduced (see Srinivas et al. (2009;; Valko et al. (2013); Chowdhury and Gopalan (2017); ;  among many others) under various names such as information gain. All these variants are in some sense equivalent to each other, in that they all capture the effective dimensionality of a RKHS, perhaps up to a logarithmic factor.
In this section, let X be a set, K : X ×X → R be a kernel, n be a positive integer, x 1:n = (x 1 , x 2 , · · · , x n ) ∈ X n , and λ > 0, K be a n × n matrix where
Remark 3.2. It is easy to see that d eff (λ, x 1:n ) is a non-negative non-increasing function of λ, it tends to 0 as λ → ∞. It is also a bounded function of λ in that d eff (λ, x 1:n ) ≤ n.
The following lemma gives a bases-independent representation of d eff ; in particular, it shows that the effective dimension is invariant to the permutation of data, therefore x 1:n in the definition of d eff can be simply treated as a set.
The following lemma gives yet another representation of d eff , which will be particularly useful when analyzing our proposed algorithm later.
The following lemma shows that the effective dimension is non-decreasing as data accumulate.
It is instrumental to see how d eff behaves under common kernels. For linear kernels, the following lemma is well-known.
Lemma 3.6 (Effective dimension under linear kernels). If X is a d-dimensional Euclidean space and For Gaussian RBF kernels, we have the following recent result. Notably, the effective dimension grows only polylogarithmically with n λ . Lemma 3.7 (Effective dimension under Gaussian RBF kernels (Altschuler et al., 2018)). Let d be a positive integer, X = x ∈ R d : x 2 ≤ 1 , and K(x, y) = e −η x−y 2 2 for some η ≥ 0, then for any λ ≤ n, 1 Also called effective degrees of freedom in Hastie et al. (2009).
Remark 3.9. Similar to d eff , d pse (λ, x 1:n ) is also a non-negative non-increasing function of λ, it tends to 0 as λ → ∞. However, in contrast to d eff , d pse (λ, x 1:n ) is not a bounded function of λ; if K is not a zero matrix, as λ → 0, it tends to infinity.
Remark 3.10. Because the determinant only changes sign when swapping rows or columns, the pseudo dimension is invariant to the permutation of data, therefore just like in the case of d eff , x 1:n in the above definition can be simply treated as a set.
The following lemma shows that d pse is at most a logarithmic factor (in terms of n λ ) larger than d eff . Lemma 3.11 ( (Jézéquel et al., 2019)).
The following lemma will play an important role in our analysis.
Lemma 3.12. The following are true: In particular, Lemma 3.12.(I) says that, similar to the effective dimension (Lemma 3.5), the pseudo dimension is also non-decreasing as data accumulate.
To conclude the introduction of pseudo dimension, let us introduce a generalization of Abbasi-Yadkori et al. (2011, Theorem 1) stated in terms of d pse in the following Lemma. Its proof is almost identical to the proof in the special case when H has a linear kernel. We also note that the inequality in the lemma visually resembles Theorem 1 in Chowdhury and Gopalan (2017), however, the quantities on the left hand side of the inequalities are actually quite different.
be a real-valued stochastic process such that η t is F t measurable, and is zero mean and R-sub-Gaussian conditioned

Covering Number of Operators
Let T : X → Y be a bounded linear operator where X and Y are normed vector spaces. N (ǫ, T ), the ǫ-covering number of T , is defined to be the cardinality of the smallest set V ⊆ Y such that for any x ∈ X, Given a real-valued RKHS H, we are interested in the covering numbers of two identity mappings, Both N (ǫ, I H, * ) and N (ǫ, I HS, * ) captures properties H. However, unlike the effective dimension introduced in Section 3.1.1 and the pseudo dimension introduced in Section 3.1.2 that depend on a scale λ, these covering numbers are data-independent and depend on a granularity ǫ instead.

Setup
Consider a Markov decision process (MDP) with state space S, action space A, transition function P : S × A → P(S), and reward function 3 r * : S × A → [0, 1]. Consider a T -step RL process. Denote by s t and a t the state and action taken in the tth step (t starts from 1), the algorithm receives reward r * (s t , a t ) after taking action a t and a new state s t+1 is sampled from P(s t , a t ).
We measure the performance of an RL algorithm by its γ-regret (Liu and Su, 2021;He et al., 2021b;Zhou et al., 2021b), defined by where V * (s) is the optimal γ-discounted return starting from state s, in the sense that and Here the multiplier (1 − γ) in (2) is only for normalization such that Regret γ (T ) ≤ T . Denote by a * (s) any action that attains V * (s) in (3).
Let H be a real-valued RKHS defined on S × A such that the corresponding kernel K : (S × A) 2 → R is bounded. Without loss of generality, we will assume K ∞ > 0; and we further assume K is properly normalized so that for any (s, a) ∈ S × A, K (s,a) H ∈ [1/2, 1].
Let us convert P into a linear operator by defining We will assume there exists an (unknown) M : B(S) → H such that The operator norm of M is defined by We assume M ≤ ρ. Similarly, for the reward function, we will also assume there exists an (unknown) r ∈ H such that Let σ ∈ [0, 1] be a bound on the stochasticity of the MDP. Specifically, for any (s, a) ∈ S × A, f ∈ B(S) such that f ∞ ≤ 1, f (s ′ ) is σ-sub-Gaussian when s ′ ∼ P(s, a). Clearly, σ can always be set to 1, and for a deterministic MDP, σ can be set to 0.

Algorithm
We propose kernelized Q-learning (KQL) (Algorithm 1), which can run in time O((T + g)T 2 |A|), where g is the time to compute x, y → K(x, y). When the kernel is linear, the running time can be improved (by special implementation) to O(T d 2 |A|), where d is the dimension of the feature space that S × A is embedded into.
We list closed-form representations of the variables maintained by Algorithm 1 below. In fact, our main results in Section 6 hold for any algorithm for which these variables are maintained.

Main Results
We now state the main result of this paper, an upper bound on the regret for KQL.
in Algorithm 1, or any algorithm that satisfies (1)-(3) in Fact 5.1 and acts to maximize Q t therein, with probability at least 1 − p, if then Let us take a closer look at how the bound depends on ρ, ǫ, σ, and λ. Note that the bound can be decomposed into three parts, involving ρ, ǫ, σ respectively: The first part, involving the complexity bound ρ, is Here d λ upper bounds a non-increasing function of λ that is bounded by T and log e(T +λ) λ log(1+1/λ) is a non-decreasing function of λ that tends to 1 as λ → 0 and tends to ∞ as λ → ∞. This suggests that λ needs to strive a balance between the two conflicting dependencies.
The second part, involving the approximation bound ǫ, is Here d λ upper bounds a non-increasing function of λ, log e(T +λ) λ log(1+1/λ)λ is a strictly decreasing function of λ, and tends to 1 as λ → ∞. This suggests that as far as the ǫ-related part is concerned, the larger the λ the better.
The third part, involving the stochasticity σ, is Here both d λ and c λ upper bound a non-increasing function of λ. log e(T +λ) λ log(1+1/λ)λ , as discussed before, is a strictly decreasing function of λ that tends to 1 as λ → ∞. log e(T +λ) λp is a strictly decreasing function of λ that tends to log e p as λ → ∞. This suggests that as far as the σ-related part is concerned, the larger the λ the better.
To conclude, both the ǫ-and σ-related parts of the regret bound prefers larger λ; however, the ρ-related part in general calls for a λ that is neither too large nor too small.
The following corollary is a direct consequence of Theorem 6.1, Lemma 3.6, Lemma 3.14.
Corollary 6.2 (Regret for linear kernels). In Theorem 6.1, if K((s 1 , a 1 ), (s 2 , a 2 )) = φ(s 1 , a 1 ) ⊺ φ(s 2 , a 2 ) where φ : S × A → R d for some positive integer d such that φ(s, a) 2 ≤ 1 for any (s, a) ∈ S × A. Then we can choose d λ = d and some c λ = O d 2 log eH(T +λ) λ such that (4) is always true, and therefore with probability at least 1 − p, Remark 6.3. Recall that in the general setting λ should be neither too large nor too small. However, since here d λ is bounded by d, which is independent of λ, if λ is sufficiently small such that λ = O(1/T ), we can make the dependency on ρ to be ρ √ T d (1−γ) 2.5 . In other words, in the linear setting, if the MDP is deterministic and the dynamics can be exactly represented by functions in H, then we can choose λ = O(1/T ) such that Comparing this with choosing λ = Θ(1), a factor of log(eT ) is reduced.
A perhaps more interesting example would be the regret bound for the widely-used Gaussian RBF kernel. The following corollary is a direct consequence of Theorem 6.1, Lemma 3.7, Lemma 3.15, Lemma 3.16.
Corollary 6.4 (Regret for Gaussian RBF kernels). In Theorem 6.1, if K((s 1 , a 1 ), (s 2 , a 2 )) = e −η φ(s1,a1)−φ(s2,a2) 2 2 for some η ≥ 0 and φ : S ×A → R n for some positive integer n such that φ(s, a) 2 ≤ 1 for any (s, a) ∈ S ×A. Then we can choose some such that (4) is always true, and therefore with probability at least 1 − p, We see that the above regret bound only differs from the bound in Corollary 6.2 in that d is replaced by O η + log e(T +λ) λ(1−γ) . This suggests that this new quantity indicates the effective dimensionality under the Gaussian RBF kernel at scale λ. Note that although a smaller η would benefit the regret bound, an η too small would violate the assumption on ρ as described in Section 4.
Remark 6.5. Again we can inspect how the ρ-related term in the bound, In other words, in the Gaussian RBF kernel setting, if the MDP is deterministic and the dynamics can be exactly represented by functions in H, then we can choose λ = Θ (1/T ) such that Comparing this with choosing λ = Θ(1), a factor of log(eT ) is reduced. Recall that in Remark 6.3, we showed that the same thing happens in the linear setting.

Experiments
We test KQL on a suite of classic control tasks included in OpenAI Gym (Brockman et al., 2016): Mountain-Car, Pendulum, Acrobot, and CartPole. The action space of Pendulum is discretized to {−1, 0, 1}, all other environments have discrete action space natively.

Methodology
For any state s and action a, let [s, a] be the concatenation of the state vector and the one-hot embedding of the action; let l be the length of state vectors. The states are first normalized such that s ∞ ≤ 1 for all s. We experiment with two types of kernels: • Linear Kernel K((s 1 , a 1 ), (s 2 , a 2 )) = [s 1 , a 1 ] ⊺ [s 2 , a 2 ] 2(l + 1) + 1 2 .
We normalize the rewards to fall within [0, 1]. Since all environments are deterministic we can let σ = 0. We also believe that for these simple environments, if a correct kernel is used, ǫ can be made infinitesimally small. Our theoretical results (Theorem 6.1) suggest that in this case we can set and our discussions in Remark 6.3 and Remark 6.5 suggest we can set We heuristically set β = √ λ 1−γ so that Q t 1/(1 − γ) at the beginning of learning, and set λ = 1 10T so that λ is large enough to not cause numerical issues.
To emphasize the test on sample efficiency, for each environment, all algorithms are only allowed 1000 steps through the OpenAI Gym interface; a reset is only allowed in the very beginning and after a done is received. We use the same discounting factor γ = 0.95 for all algorithms and all environments.

Results
The results are shown in Table 1. As we can see, the linear kernel performs poorly on all tasks. In fact, its performance is not noticeably better than a random policy. Without handcrafted or learned feature embedding, the value function is highly non-linear; thus linear kernel suffers from huge approximation error. DQN makes progress on most tasks, with the exception of MountainCar, which requires more than random exploration in order to succeed with a very limited amount of interaction. Remarkably, the Gaussian RBF kernel achieves high return and performs best on all tasks, compensating for its long running time by its far superior sample efficiency.

Where Next
We have demonstrated that KQL is both theoretically sound and empirically promising. However, kernel methods are known to suffer from the curse of kernelization -their time complexity has a super-linear dependency on the number of samples, KQL is no exception.
There are two standard ways to trade sample efficiency for time complexity in kernel-based online learning: one is sparsification, which aims at keeping the number of support vectors d ≪ T by various strategies (see e.g. Engel et al. (2004); Sun et al. (2012); Calandriello et al. (2017) and the discussion in Lu et al. (2016, Related Work)); the other is kernel approximation, which aims at projecting vectors in an RKHS into a Euclidean space, for example, using random Fourier features, and reduce the kernel setting to the linear setting (Lu et al., 2016;Jézéquel et al., 2019). Given its already impressive performance even without any kernel sparsification or approximation, it is not hard to believe that with proper acceleration, KQL is able to tackle more challenging tasks such as Atari games (Bellemare et al., 2013). We leave it as future work to investigate these directions.
Z. Zhang and X. Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. arXiv preprint arXiv:1906.05110, 2019.
Z. Zhang, X. Ji, and S. Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon.

A Proof of Lemma 3.16
Let N be the set of non-negative integers. For any multi-index ν = (n 1 , n 2 , · · · , n d ) ∈ N d , define |ν| = n i=1 n i . The following facts will be useful. Fact A.2 (Taylor expansion). For any nonnegative integer n and t ≥ 0, Define the function It is well-known that B = e ν : ν ∈ N d is an orthonormal basis for H (see e.g. Steinwart et al. (2006, Theorem 3.7)). Consequently, e ν1 ⊗ e ν2 : ν 1 , ν 2 ∈ N d is an orthonormal (Schauder) basis for B HS (H). Now note that where (a) is due to Cauchy-Schwarz and (b) is due to Fact A.1. Next we introduce for all positive integer N two orthogonal projections: P N , which is the projection onto span {e ν1 ⊗ e ν2 : |ν 1 | < N, |ν 2 | < N }, and Q N , which is the projection onto P ⊥ N . Note that where (a) is due to Cauchy-Schwarz and (b) is due to Fact A.1 and (c) is due to Fact A.2. Note that we can choose N = 2 ln 2 √ 2 ǫ + e 2 η such that I HS, * Q N ≤ ǫ/2. Finally, note that ln N (ǫ, I HS, * ) ≤ ln (N (ǫ/2, I HS, * P N ) · N (ǫ/2, I HS, * Q N )) = ln N (ǫ/2, I HS, * P N ) where in (a) we used I HS, * P N ≤ I HS, * = 1 and the fact that a n-dimensional unit ball can be ǫ-covered by (1 + 2/ǫ) n points.

B Proof of Other Lemmas
Proof of Lemma 3.4. Let W = (Σ + λI) −1 , note that where (a) is due to Lemma 3.3.
Proof of Lemma 3.5. Let W n = ( n i=1 K xi ⊗ K xi + λI) −1 and f = W n−1 K xn . It is easy to verify that Therefore, where (a) is due to Lemma 3.4 and (b) is due to (6).
Proof of Lemma 3.6. Let Σ = n i=1 x i x ⊺ i . By Lemma 3.3 we have that d eff (λ, x 1:n ) = tr (Σ + λI) −1 Σ . Let λ 1 , λ 2 , · · · , λ d be the eigenvalues of Σ, we have tr (Σ + λI) −1 Σ = n i=1 λi λi+λ ≤ d. Proof of Lemma 3.12. First note that since Σ i−1 /λ is a linear operator of rank at most i−1, det (Σ i−1 /λ + I) is well-defined. Therefore, e dpse(λ,x1:i) e dpse(λ,x 1:(i−1) ) − 1, where (a) can be proved for example using the same argument used for Cesa-Bianchi and Lugosi (2006, Lemma 11.11). Note that (7) already implies (I), since a norm is non-negative. Next, it is easy to verify that K xi 2 (Σi−1+λI) −1 ≤ 1/λ and that x ≤ b ln(1+b) ln(1 + x) for any x ∈ [0, b]. Therefore, where (a) is due to (7). Therefore (I) is proved, since a norm cannot be negative. Note that the above argument is still true if we replace x i by an arbitrary x ∈ X. Consequently, denote by [a, b] the concatenation of sequence a and sequence b, we have where we used (I) in (a), (b), (c) and the nonnegativity of d pse in (b); in particular, in (b) we canceled the (i, τ )th term in (A) with the (2i + 1 − τ, i + 1)th term in (B), where the first index of a term is its position in the first summation and the second index is its position in the second summation. This concludes the proof of (II).
Proof of Lemma 3.14. In the case of linear kernel, for any x ∈ H, x H = x * = x 2 ; and for any linear operator T over X, T * ≤ T F = T HS . Because a n-dimensional unit ball can be ǫ-covered by (1 + 2/ǫ) n points, the lemma follows immediately.

C Proof of Main Results
We will prove Theorem 6.1 in this section. We first introduce some notations. For any t ∈ [T ], let prev(t) For any p > 0, let E p be the event that for any s ∈ S, a ∈ A, t ∈ [T ], Q t (s, a) − Q * (s, a) − γ M * V t−1 − V * (s, a) ≤ (Φ + Ψ p ) · K (s,a) Wt + 2ǫ 1 − γ .
where V 0 can be any function that is bounded in [0, 1/(1 − γ)]. We start from some auxiliary lemmas.
Lemma C.7. For any p > 0, E p happens with probability at least 1 − p.
Proof. First note that for any t ∈ [T ], Q * = r * + γM * V * , and consequently To proceed, note that for any t ∈ [T ], Let us bound E 1 (s, a), E 2 (s, a), E 3 (s, a), E 4 (s, a) separately. First note that |E 1 (s, a)| ≤ λ r W t K (s,a) + λ (γM V * ) W t K (s,a) (a) ≤ λ · r Wt + γM V * Wt · K (s,a) Wt where (a) is due to Cauchy-Schwarz and (b) is due to the upper bound in Lemma C.1.
Also note that Therefore, we have that Now we are ready to prove our main theorem.


Named Sets as an Efficient Tool for Modeling Data Relationships in Database Models "2279

An important problem for databases is the unification of utilized data structures and amplification of operation tools. Here, after a brief overview and analysis of database models, we demonstrate that all considered data can be reduced to systems of named sets allowing representation of the described database models as special cases of the named-set database model, which provides efficient operations for data mining, information extraction, and database management.

Introduction
Data are representations and containers (carriers) of information. Data andtheir relationships form data structures. That is why modeling data relationships in the context of data and knowledge structures is critically important for organization and optimization of information processes in databases and beyond.
Data have different structures and both data processing in general and data mining in particular depends on these structures. For instance, the well-known computer scientist and mathematician Yuri Gurevich concluded his lecture [1] on the advancement of theoretical computer science with the statement that to be useful for database technology, computational models have to work with structures and not with strings of symbols. The most popular data structures include Boolean values, characters, integers, fixed-precision number values, floating-point number values, arrays, records, lists, streams, sets, multisets, stacks, queues, and graphs, just to mention the most important of them. Here, in addition to these conventional data structures, we consider named sets and chains of named sets as the fundamental data structures for modeling data relationships in database models.

Database Models
As Angles and Gutierrez write, from a database point of view, the conceptual tools that make up a database model should at least address data structuring, description, maintenance, and a way to retrieve or query the data [2]. These principles imply that a database model consists of three components: a system of utilized data structure types with their logical and operational organization; a system of operators and inference rules; and a system of integrity rules [3]. The logical structure of a database includes the relationships and constraints that determine how data can be stored and accessed. As a rule, database models mainly pay attention to utilized data structures, which are represented by a database model. Let us consider the main database models used for storing and preserving information.
The hierarchical database model is the oldest being developed by IBM for information management system (IMS) [4]. In it, data are organized in the tree structure.
The network database model represents data with records and sets. Records contain fields, which may be organized hierarchically, while sets define one-to-many relationships between records. This model is an expansion of the hierarchical model allowing many-tomany relationships in a tree-like structure.
The flat(or table) database model consists of a single, two-dimensional array of data elements, where all members of a given column are assumed to be similar values and all members of a row are assumed to be related to one another having the same type. The flat model predates the relational model. The relational database model was introduced by Codd [5] and highlights the concept of abstraction levels by introducing the idea of separation between physical and logical levels. It is based on the notions of sets and relations. Due to its ease of use, it gained wide popularity among business applications.
The multivalue database model is an extension of the relational model. In it, a field/attribute can have several values at the same time.
The semantic database model represents objects and their relations in a natural and clear way, providing users with tools to correctly reflect the desired domain semantics. The entity-relationship model is an example of semantic database models [6].
The resource space database model (RSM) is a non-relational data model based on multidimensional classification [7].
The object-orienteddatabase model is based on the object-oriented paradigm representing data as a collection of objects that are organized into classes and assigned complex values [7].
The graphdatabase model represents objects and their relations in the form of a graph overcoming the limitations imposed by traditional database models with respect to capturing the inherent graph structure of data appearing in applications such as hypertext or geographic information systems, where the interconnectivity of data is an important aspect [2].
The semistructureddatabase model exemplifies data with a flexible structure, for example, documents or Web pages. Semistructured data are neither raw nor strictly typed, as in the conventional database systems [8].
The XML (eXtensible Markup Language) database model focuses on information with tree-like structure [9].
The named-set database model represents information in the form of systems of named sets such as named set chains [10].

Named Sets in Database Modeling and Data Representation
Here we show that all of these database models can be treated as special cases of the named-set database model since all utilized data structures are either named sets or systems of named sets.
So, the question is as follows: Why are named sets really essential, and what is so specific about them?
First, it is proved that any mathematical structure is a named set or is built of named sets and thus, the named set is the most fundamental structure in all mathematics [11]. For instance, functions, relations, variables, graphs, multigraphs, and morphisms (arrows) in categories are special cases of named sets. Ordinary sets are also specific named sets, namely they are singlenamed sets since all elements in a set with the name, say Q, have the common name "an element of the set Q" [11].
Second, we see that named sets are vital for representation of data, knowledge, and information as well as all cognitive processes and communication [12]. Taking any book on databases, we see many examples of named sets (cf., for example, [13]).
Third, it is proved that the named set (also called fundamental triad) is the most basic structure in nature [12]. As a consequence, named sets have become ubiquitous in modeling natural systems.
Let us consider the basic definition.

Definition 1. (a)
A basic named set, also called a basic fundamental triad, is a triad X = (X, f, N) with the following visual (graphic) representation: f X→N (b) A bidirectional named set, also called a bidirectional fundamental triad, is a triad X = (X, f, Z) with the following visual (graphic) representation:

f X↔N
In this triad X = (X, f, N), the components X and N are two objects and f (in case a) is a correspondence (e.g., a binary relation) from X to N and (in case b) is a correspondence (e.g., a binary relation) between X and Z, which goes in two directions. With respect to X, the object X is called the support of X and denoted S(X), the object N is called the component of names (reflector) or set of names of X and denoted N(X), and the object f is called the namingcorrespondence (reflection) of X and denoted r(X). It means that X = (S(X), r(X), N(X)). Note that in X, components X and N are not automatically sets, while f is not necessarily a mapping or a function even if X and N are sets. For instance, X and N are sets of words and f is an algorithm.
The standard example is a basic named set (basic fundamental triad), in which X consists of people, N consists of their names, and f is the correspondence between people and their names.
Let us analyze the considered database models in the context of named sets. Hierarchical data are organized as tree structures, which are chains of named sets starting with the root of the tree and ending with its leaves [14]. Consequently, the hierarchical database model is a special case of the named-set database model.
Any network in general and a network of records, in particular, have the structure of a graph. A graph consists of vertices (nodes) and edges connecting some vertices. If V is the set of all vertices and E is the set of all edges in graph G, then this graph is a named set (V, E, V). Consequently, the network database model is a special case of the named-set database model. Note that as records contain fields and fields are named sets with values as their names, any network of records is a nested named set [15].
Any two-dimensional arrays in general and two-dimensional arrays of data elements, in particular, are nested named sets [15]. Consequently, the flat database model is a special case of the named-set database model.
Relations are special cases of set-theoretical named sets [11]. Consequently, the relational and multivalue database models are special cases of the named-set database model.
Objects (entities) with relations form a named set [11]. Consequently, the semantic database model is a special case of the named-set database model.
Any classification is a set-theoretical named set [11]. Consequently, the resource space database model is a special case of the named-set database model.
In the object-oriented approach, data are formed as objects and each object has a name, set of attributes, and behaviors. Thus, the support of an object consists of its name which is connected to its attributes and behaviors. This is the structure of a named set. In addition, any set of objects is the named set, which is the union of the named sets of individual objects [11]. Consequently, the object-oriented database model is a special case of the named-set database model.
As it was demonstrated that any graph is a named set, the graph database model is a special case of the named-set database model.
Finally, as any structure is built from named sets, the semistructured and XML database models are special cases of the named-set database model. For XML data, this was demonstrated in [16].

Conclusions
An important peculiarity of utilization of named sets in databases is that algorithms in general, and software systems in particular, for operation with data are also specific named sets and systems of named sets. Namely, they are algorithmic named sets and their systems (i.e., such named sets in which the relation f is an algorithm or a program) [11,17].
An important advantage of the named-set database model is not only structural unification but also operational affluence. Indeed, manipulation with data demands utilization of various operations and, in the case of using named sets for data representation, a variety of operations such as mappings of different kinds, union, intersection, difference, renaming, naming, interpreting, and reinterpreting, and their properties are provided by the theory of named sets [11].
Operating with data in the named-set database model involves structural recursion capturing the system's repeating patterns. As a result, an important direction for future research is exploration of structural recursion in the context of named sets and its application to the problems of data search, as well as to database development and management.
Nesting is an important phenomenon in many areas in general and the database technology in particular. Nested structures are efficiently modeled by nested named sets [15]. Thus, one more interesting direction for future research is to study nested named sets and operations in their domain with the goal of their employment in database operation and control.