Afshin Moin
email: afshin2927@yahoo.com

A Unified Approach To Collaborative Data Visualization *

Much efforts have lately been concentrated on increasing the precision of recommendations following the Netflix Prize competition. Recently, many researchers and industries have noted that other factors like adequate presentation of the results can add more utility to a recommender system than slight improvement in the precision. In this paper, we suggest a methodology for user-friendly representation of recommendations to the end users. Our scheme unifies the two objectives of prediction and visualization in the core of a unique approach. Users and items are first embedded into a high dimensional latent feature space according to a predictor function, particularly designated to meet visualization requirements. The data is then projected into a 2-dimensional space by Curvilinear Component Analysis (CCA). CCA draws personalized Item Maps (PIMs) representing a small subset of items to the active user. The intraitem semantic correlations are preserved in PIMs which is inherited from the clustering property of the high-dimensional embedding space. Our prediction function and the projection method are both non-linear to increase the clarity of the maps and to limit the effect of projection error. The algorithms are tested on three versions of the MovieLens dataset and the Netflix dataset to show they combine good accuracy with satisfactory visual properties. Moreover, a novel offline methodology is suggested to measure the quality of PIMs.

INTRODUCTION

Collaborative Filtering (CF) [START_REF] Linden | com recommendations: item-to-item collaborative filtering[END_REF][START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF][START_REF] Bell | Scalable collaborative filtering with jointly derived neighborhood interpolation weights[END_REF][START_REF] Deshpande | Item based top-n recommendation algorithms[END_REF] is the prevalent approach to Recommender Systems (RS). It extracts relevant items by tracing the similarities between the past behavior of users. Following the Netflix Prize competition [START_REF] Bennett | The netflix prize[END_REF], most works on CF concentrated on improving the prediction precision [START_REF] Koren | Collaborative filtering with temporal dynamics[END_REF][START_REF] Bell | Scalable collaborative filtering with jointly derived neighborhood interpolation weights[END_REF][START_REF] Salakhutdinov | Probabilistic matrix factorization[END_REF]. Nevertheless, precision is not the only determining factor for the success of RSs. It is also important that results are represented as informative as possible because their careless presentation wastes efforts made to enhance precision. Most often, recommendations are presented in the form of a ranked list. Users have multiple interests, and are likely to change their preferences over time [START_REF] Widmer | Learning in the presence of concept drift and hidden contexts[END_REF][START_REF] Koren | Collaborative filtering with temporal dynamics[END_REF][START_REF] Kolter | Dynamic weighted majority: An ensemble method for drifting concepts[END_REF]. In the same way, one user account may delegate several persons, each having different taste and needs. Though, ranked lists do not unveil the correlation between items unless the user knows them a priori. This issue limits the benefit of recommender systems as it prevents the users from making a correct selection based on their current needs.

In this paper, we suggest a Matrix Factorization-like (MF) recommendation algorithm combined with a non-linear projection technique arranging the results of CF in the form of 2-dimensional maps. This latter is a better alternative to ranked lists as it arranges items based on their similarity. Of course, other solutions like showing the content information of items may also be considered. However, it requires expensive gathering and involved cleaning tasks which companies try to avoid. In addition, interpreta-tion of a visual map is more convenient and quite intuitive. MF RSs [START_REF] Drineas | Competitive recommendation systems[END_REF][START_REF] Bell | Modeling relationships at multiple scales to improve accuracy of large recommender systems[END_REF] embed users and items in a latent feature space. Missing ratings are then estimated through the inner product of user and item coordinates. MF has been noted on passing to have the property of putting similar items close to each other in the latent feature space [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. Nevertheless, there are two barriers against their application to draw 2-dimensional maps. First of all, the existing predictor functions are not apt for visualization purposes. Namely, users link intuitively the relevance between users and items to their Euclidean distance on the map. However, the existing predictors, generally variants of the inner product of vectors, need other information (e.x. the angle between user and item coordinates vector). Secondly, MF approaches need more than 2 dimensions to reach their optimal precision. Consequently, proper projection methods must be picked up preserving as much information as possible.

Our approach is composed of two phases: the embedding phase and the projection phase. The first phase embeds users and items into a high dimensional space based on a predictor aimed at meeting visualization requirements. This predictor is a decreasing function of the Euclidean distance between the corresponding user and item. In the second phase, data is projected from the high dimensional space into a 2-dimensional map. Our design goal is to make special emphasis on the interpretability of results for the end user such that interesting items are easily distinguishable from uninteresting ones. Moreover, the quality of the maps must be as prone as possible to the inevitable projection error. To achieve these goals, we rely on a non-linear prediction function for the embedding phase; Nonrelevant items get further from users with a rate larger than linear. This improves the separation of relevant items from irrelevant ones. Furthermore, they are less probable to appear close to the user as a result of projection error during the projection phase .

Our projection method relies on the assumption that far away items are less probable to be compared. Hence when necessary, preservation of close distances must be preferred over preservation of long ones. Such projection can not be done using classic linear projection methods like MDS. We use Curvilinear Component Analysis (CCA) as our projection technique. Preferring the conservation of short distances to long ones, not only does this nonlinear projection method covers the effects of the projection from the eye of the user, but also lends itself well to our non-linear prediction function that places irrelevant items much further than relevant ones. The original CCA approach is altered to give more weight to preservation of distances w.r.t the active user. We call the resulting map personalized Item Maps (PIMs). All PIMs are presented with the same visual parameters such that comparison between PIMs of different users is meaningful. PIMs represent a number of items to a specific user. They are helpful in applications like visual recommendation or in scenarios where users need a visual comparison of a number of items. In a PIM, items are placed around the active user such that their relevance decreases with their distance from her.

The prediction precision of our approach is validated by running experiments on the three versions of the MovieLens dataset and the Netflix dataset. The quality of the resulting map is evaluated using a novel offline methodology which is another contribution of this paper. This method measures the inconsistency of PIMs, that is, the cases when an item with a lower predicted score lies closer to the user than a more relevant item.

Two common approaches to CF are neighborhood-based methods [START_REF] Linden | com recommendations: item-to-item collaborative filtering[END_REF][START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF][START_REF] Bell | Scalable collaborative filtering with jointly derived neighborhood interpolation weights[END_REF][START_REF] Deshpande | Item based top-n recommendation algorithms[END_REF] and Matrix Factorization (MF) [START_REF] Hofmann | Latent semantic models for collaborative filtering[END_REF][START_REF] Koren | Collaborative filtering with temporal dynamics[END_REF][START_REF] Salakhutdinov | Restricted boltzmann machines for collaborative filtering[END_REF][START_REF] Khoshneshin | Collaborative filtering via euclidean embedding[END_REF]. The latter, being less complex and more exact, leverages the whole ratings to embed users and items in a latent feature space. We concentrate on this method and suggest a variant creating an embedding suitable for visual representation of CF data.

Visualization of high dimensional datasets has an important role in their understanding. Many information visualization solutions have been suggested to this problem. A very common approach is to model the information as a graph such that nodes represent data points and edges represent relations between them. Classic graph drawing algorithms like Spring Embedder [START_REF] Eades | A heuristic for graph drawing[END_REF] and Spring electrical model [START_REF] Fruchterman | Graph drawing by forcedirected placement[END_REF], or more recent methods like Maxent stress model [START_REF] Gansner | A maxent-stress model for graph layout[END_REF] and FlexGD [START_REF] Kermarrec | Flexgd: A flexible force-directed model for graph drawing[END_REF], can consequently be used for their visualization. In the same line of work, [START_REF] Gansner | Putting recommendations on the map: visualizing clusters and relations[END_REF] suggest a method for visualizing graphs and clusters in the form of a geographical map. Interpretation of such maps is easy and intuitive for the users.

Graph drawing has also been applied to the context of collaborative filtering in [START_REF] Xiong | Visualizations of collaborative information for end-users[END_REF]. The data is modeled as a bipartite graph with vertices representing users and items and edges representing the interactions. Graph drawing algorithms are aimed at generation of readable graph layouts based on a number of predetermined aesthetic criteria. Therefore, the resulting visualizations are readable and pleasing. However, the same criteria prevent them from having enough predictive capability, a property which is central in this paper. In particular, they offer no prediction function according to which a quantitative item score can be estimated for a user. Some other works like [START_REF] Chen | Visualizing collaborative filtering in digital collections[END_REF][START_REF] Bostandjiev | Tasteweights: a visual interactive hybrid recommender system[END_REF] suggest other visualization strategies for CF which are radically different from visualization on a map. In [START_REF] Chen | Visualizing collaborative filtering in digital collections[END_REF], the NEAR panel is suggested to manage digital collections. A graphical user interface is designed in the form of a hierarchical browser. This interface shows the latent similarities between items to the end user in a visual manner. [START_REF] Bostandjiev | Tasteweights: a visual interactive hybrid recommender system[END_REF] is a visual interactive recommender system which is also context aware.

In the context of neighborhood-based CF, classical Multi Dimensional Scaling (MDS) [START_REF] Cox | Multidimensional Scaling, Second Edition[END_REF][START_REF] Borg | Modern Multidimensional Scaling: Theory and Applications[END_REF] is directly applicable. Namely, a symmetric matrix of item-item dissimilarities is computed. A userspecific list of top-k relevant items is then visualized through MDS. This method has the drawback of not mapping a user together with her recommended items, as similarity is only defined between items or users but not between a user and an item. Furthermore, these item-item dissimilarities are computed based on measures like cosine or Pearson correlation. These measure are local and do not leverage the whole dataset as our approach does. In other words, MF and neighborhood-based approach reveal different types of correlation within data (global vs. local). Our experiments shows that there is almost no correlation between cosine and Pearson similarity of items and their relative position in an MF map.

[5] presents Latent Markov Embedding (LME) to generate visual music playlists for users. This machine learning algorithm models the problem of playlist generation as a regularized maximum likelihood embedding of Markov chains in the Euclidean space. Their approach is similar to language modeling techniques for speech recognition and modeling. It lends itself well to sequence prediction problems. However, its application to non-binary rating estimation is not straightforward.

The advantages of collaborative filtering via Euclidean Embedding is also discussed in [START_REF] Khoshneshin | Collaborative filtering via euclidean embedding[END_REF]. Their prediction function includes an item-dependent feature. Hence, the distance between a user and an item is not the only determining factor for computation of recommendations. Consequently, it happens occasionally that items with higher predictions lie further from a user because of having a smaller item-dependent feature. The projection applied in [START_REF] Khoshneshin | Collaborative filtering via euclidean embedding[END_REF] is MDS.

Our work is original in applying a non-linear prediction function u p i q j q (a) SVD-like predictor. j is more relevant to u than i, i.e. pu • q j > pu •q i , while it is further from her, i.e. pu -q j > pu -q i . j q i q u p (b) Visual predictor. The more relevant item j is closer to the user u than i. The distance from the origin and the angle between the user and item coordinate vectors are not central. allowing for easier separation of relevant and non-relevant items, whose results are consequently passed to a proper non-linear projection method, i.e. CCA. This projection method improves the quality of the resulting maps and decreases the influential visual errors. In particular, we will see in the experiments that the quality of maps generated by CCA outperforms considerably the quality of those issued by MDS. As far as we know, such a combination of non-linear embedding and projection techniques have not been used in CF so far. Meanwhile, our validation methodology is a novel way for quantitative measuring of the quality of the recommendation maps.

MATRIX FACTORIZATION FOR VISUAL PREDICTION

Singular Value Decomposition (SVD) [START_REF] Golub | Matrix computations[END_REF] is the most common MF approach to CF. SVD is computable if all matrix entries are known.

In CF however, the majority of ratings are missing. A common alternative, known as the SVD-like approach, is to estimate the latent features through minimizing a regularized cost function:

min p * ,q * ,r * ∈R (rui -pu • qi) 2 + λ( pu 2 + qi 2 )
,

where pu = (xu(1), • • • , xu(k)) and qi = (yi(1), • • • , yi(k))
are the latent features of user u and item i in an embedding space of k dimensions. The first term strives to minimize the prediction error over the observed ratings. Since the goal is to predict future ratings, the second terms is added to avoid overfitting the observed ratings. λ is called the regularization factor. This function is minimized using the stochastic gradient descent method. Users and items are moved iteratively by a step length γ in the opposite direction of the gradient until the change of user and item coordinates is negligible. At each iteration, coordinates are updated as:

pu ← pu + γ(euipu -λqi) qi ← qi + γ(euiqi -λpu) ,
where eui = rui -rui is the prediction error of item i for user u. λ and γ are optimized by cross validation on a smaller subset of the ratings. This approach is very similar in the spirit to MF approaches, as it embeds users and items in a low dimensional feature space. Despite, since it is not formulated in the form of a classic SVD, we refer to it as an SVD-like approach.

Basic Visual Predictor

The original SVD-like approach is not suitable for visualization purposes. The inner product function, used in the SVD-like approach, is a function of the magnitude of the vectors and the angle between them. Consequently, it can place a less relevant item closer to a user than a more relevant one. This presentation is misleading because users intuitively interpret closer items as more relevant. More specifically, the inner product between the coordinates vector of a user, say pu, and a far item, say qj, may be a larger value than the inner product of pu and the coordinates vector of a nearby item, say qi. Such a problem does not arise, if the predictions are purely a function of the Euclidean distance, as the relevance between a user and an item is computed directly from their distance. Figure 1 illustrates why the inner product function does not conform with visualization requirements, while the visual predictor based on the Euclidean distance does. Now, we come to the definition of the visual predictor. Let rui = f ( pu -qi ) be the predicted rating of user u for item i. We set an inverse relation between the distance of an item from a user and the respective predicted value. The objective estimation function is then: rui = 1

1 α pu -qi + β . (1)
The cost function to minimize is:

min p * ,q * ,r * (rui -rui) 2 + λ( pu 2 + qi 2 ).
The minimization is done using stochastic gradient descent. Coordinates are updated at each iteration as:

pu ← pu -γ(eui (qi -pu) + λpu) qi ← qi -γ(eui (pu -qi) + λqi) , = r2 ui α pu -qi .
α and β are found by cross validation.

Improved Visual Predictor

The precision of the visual predictor is worse than the SVD-like approach. To improve the results, we set α and β as user-specific variables. This helps modeling users' behavior in finer levels, giving users and items higher degrees of freedom to take position in the embedding space. The prediction function becomes:

rui = 1 1 αu pu -qi + βu .
The regularized cost function is:

min p * ,q * ,r * ,α * ,β * (rui -rui) 2 + λ( pu 2 + qi 2 + α 2 u + β 2 u ).
The coordinates are updated using the following equations:

         pu ← pu -γ(eui (qi -pu) + λpu) qi ← qi -γ(eui (pu -qi) + λqi) , = r2 ui αu pu-q i . αu ← αu + γα(eui /αu -λαu) βu ← max{βu -γ β (eui r2 ui + λβu), β min u }
We observed during the experiments that the algorithm needs different step lengths for α and β to achieve optimal performance. We set γα = 9γ and γ β = γ/29. We also observed that for a few users βu becomes negative. In order to prevent it, we set a minimum value β min u > 0 for βu. This is a necessary condition for unification of the scale of PIMs in Section 4. We compare different predictors on the MovieLens and Netflix datasets. These are standard datasets used in many reaseach works. Table 1 summarizes some properties of the datasets. MovieLens dataset is provided by GroupLens team in three versions [START_REF] Grouplens | MovieLens Datasets[END_REF]. Each user has rated at least 20 movies. The algorithm is trained on 95% of the data. Predictions are made on the remaining 5%. To form the training and test sets, we have split each user profile into 20 uniform regular slices. 19 slices are chosen as the training profile, while the remaining one serves as the test profile. This way, we assure there is at least one rating in each user's test profile. The Netflix data set was made public for the Netflix Prize competition [START_REF] Bennett | The netflix prize[END_REF]. The dataset includes 100, 480, 507 ratings. 1, 480, 300 of the same ratings were provided as the probe set for test purposes. We trained our algorithm on all ratings, after having discarded those included in the probe set. The predictions are made on the probe set. Both MovieLens and Netflix are based on a 5-star rating scheme, that is, users rate movies between 1 and 5 stars. While the real ratings are integers, the predictions need not be. In our algorithm, predicted ratings are real numbers. We compare the performance of different predictors using the Root Mean Square Error defined as

Dataset

RMSE = r ui ∈R T est (r ui -r ui ) 2 |R T est |
, where RT est is the set of ratings in the test set. The parameters of all algorithms are well tuned to have a fare comparison. It is seen that the precision improves with the number of dimensions up to some threshold. After that, the error increments because the data is not enough to train extra dimensions. In other words, the larger the dataset, the more dimensions can be trained.

The results are summarized in Figure [START_REF] Bennett | The netflix prize[END_REF]. For the small dataset of MovieLens100K, precision gets worse because the data is not enough to train the new variables. However, interestingly, it is almost as precise as the SVD-like approach for larger datasets. The difference in precision is always less than 0.01, being 0.0096, 0.0032 and 0.0057 for MovieLens1M, MovieLens and Netflix, respectively. This allows for visual representation of the results without considerable loss in precision.

PERSONALIZED ITEM MAP

Our final objective is to build Personalized Item Maps (PIMs). One possible solution is to take a desired set of items with a user and apply classical MDS. This approach has been used in [START_REF] Khoshneshin | Collaborative filtering via euclidean embedding[END_REF]) for example. Though, no quantitative evaluation of the resulting maps is provided. It is a well-known fact that classical MDS is equivalent to PCA provided the data to be projected contains distances, which is the case in our application. PCA is a linear mapping preserving the distances as much as possible, but giving the same weight to all distances. We observed during simulations that only in a few cases does PCA show acceptable performance. For the majority of the users, it disturbs so much the original distances that they no more conform to the predicted ratings.

In order to increase the quality of PIMs to an acceptable level, compromises should be made in favor of preserving more important distances. We use Curvilinear Component Analysis (CCA) [START_REF] Demartines | Curvilinear component analysis: a selforganizing neural network for nonlinear mapping of data sets[END_REF] being a non-linear mapping technique prioritizing preservation of shorter distances over longer ones. In other words, CCA gives priority to the preservation of local topology. This property of CCA is also in line with the hyperbolic relation we set in Section 3 be- tween the predicted ratings and the Euclidean distance, as such relation emphasizes further closeness of relevant items. CCA starts from projecting long distances, and overriding them by shorter ones whenever compromises must be made. We have slightly altered the original CCA approach to give more weight to the preservation of distances w.r.t. the active user. The user is the central entity for whom the map is prepared. Hence the conformance between the recommended item scores and their distance from the user is more important than preserving the distance between two items. The customized cost function of CCA to be minimized is:

E = 1 2 i j =i (Xij -Yij) 2 F (Yij, λy),
where

F (Yij, λy) = 1 if Yij ≤ λy 0 if Yij > λy .
Xij and Yij are the distances in the original and the output space, respectively. i and j may refer either to an item or to the active user. We use the principal components as the initial distribution of the points. F (Yij, λy) is the step function discarding all distances larger than λy in the output space. λy is decreased per cycle in order to prioritize shorter distances in the output space over longer ones.

The cost function can be minimized using the usual stochastic gradient descent approach. However, the complexity of each iteration cycle would be as O(n 2 ). To decrease the complexity, a different procedure was proposed in [START_REF] Demartines | Curvilinear component analysis: a selforganizing neural network for nonlinear mapping of data sets[END_REF]. Instead of moving every point according to the influence of all other points, one random point is fixed. Other points are moved with respect to the fixed point, but without consideration of the mutual influence between them. This approach reduces the complexity of each cycle to O(n). The cost may occasionally increase in each cycle, but it decreases in average. If F (Yij, λy) is the step function, the movement of each point j w.r.t the fixed point i is:

∆yj(i) = α(t)F (Yij, λy)(Xij -Yij) yj -yi Yij ∀i = j.
λy is decreased per cycle, starting with λ0 and ending with λt max :

λy(t) = λ0( λt max λ0 ) t/tmax .
For each user we set λt max = du, where du = αu( 1 ru -βu) is the target distance corresponding to the average rating of user u. An item is relevant if its distance from the active user is less than du. Setting λt max = du ensures that items within some relevant distance from the user on the output space are not discarded until the end of the execution. In our experiments, we set λ0 = 2.0. The algorithm is run a number of cycles on the active user and the selected items, denoted by Qt. In order to give more weight to the preservation of the distances w.r.t the active user, whenever the fixed point is an item, the algorithm is run one extra time on the active user with probability 0.2. This strategy can also be validated from a game theoretical point of view. Namely, each point of the data moves the others in the goal of aligning their position in the output space with their original distances from it. Since the algorithm is run in average 0.2 |Qt| times more on the active user, compromises are made to her benefit.

Application of user specific parameters to the visual predictor leads to different interpretations of distance in PIMs. It would be nice that all PIMs are represented in the same scale such that users can compare their PIMs with each other. To unify the scale of PIMs, we first set the origin to the position of the active user (pu = 0), and reassign all the item coordinates in the translated coordinate system. We look for a transformation such that the predictions are made with the same α and β for all users:

rscaled ui = 1 1 α q scaled i + β .
Setting runscaled ui = rscaled ui , we obtain:

q scaled i = α αu q unscaled i + α(βu -β).
Since the Euclidean distance is non-negative, q scaled i ≥ 0. This condition is satisfied for all users if β ≤ β min u . The above equation is then held if:

q scaled i = α αu q unscaled i + q unscaled i q unscaled i α(βu -β).
In our experiments we set α = 2.5 and β = β min u = 0.05. Figure 3 compares the PIM of an anonymous MovieLens user projected once from an improved visual predictor latent feature space and once more from an SVD-like latent feature space. We project from a 20-dimensional improved visual predictor latent feature space and a 10-dimensional SVD-like latent feature space as 10 and 20 dimensions correspond to the best performance the respective algorithm. Shown in the figures, are the movies in the user's test profile together with a number of movies previously rated by her. Scores of the test items are predictions computed in the high dimensional feature space. Notice we would like the predicted rating to be a decreasing function of the distance in the visual latent feature space. Then, the consistency between the predicted ratings and the distance of the user from the corresponding item on the visual predictor PIM is a measure of how much the original distances have been preserved. It is seen in the PIM generated from the visual latent feature space (Figure 3a) that more relevant items are closer to the user than less relevant ones. The semantic correlation between items is preserved in a very good level. The movies Friday and Clerks on the top of the map are both comedies. In the same way, St. Elmo's Fire and ThreeSome are movies for teenagers with a background of romance and comedy. An American in Paris and Willy Wonka & the Chocolate Factory are both musicals. This map can help the user choose a movie similar to one of her previous favorites based on her mood in the time of selection. In contrast to the PIM of the improved visual predictor, it is seen in Figure 3b that the PIM projected from the SVD-like latent feature space does not place more relevant items closer to the user in general. PIMs are also useful in offering diverse recommendations to a user. Diverse recommendations entice users to go through new experiences in their consuming behavior. If the user views a cluster of recommended items on her PIM, none of which is known to her, she is encouraged to try them. One way to validate PIMs is through user studies. This method would need a number of users to test different methods of presentation and report on their quality. However, arranging such surveys for a large group of users is not straightforward unless for large industries. As a result, we suggest a novel offline validation methodology for evaluation of the quality of PIMs. Our method is based on a set of assumptions about the behavior users are likely to show when they encounter a map of products. We assume they are more likely to complain about the inconsistency between the recommended scores of two items and their distance from the active user provided that (1) those items are close on the map, (2) they are about the same radial line from the user. If none of these is true, we ignore the inconsistency between the recommendations and the distances, as such items are less likely to be compared. Namely, they are in very different regions of the map; It is therefore less natural for the users to compare them. In addition, they are deemed to be different types of product due to the clustering property of the embedding space. With these assumptions in mind, we define a region around each item where the items within are more likely to be compared. This region is the union of a circular area around the item and a conical area whose apex is on the user and who contains the item. We call this area Au(i) for the PIM of user u. Figure 4 shows Au(1) for a typical user and Movie 1 in her map. In our simulations, the radius of the circle is set to 0.2 times the length of the drawing area and the internal angle of the cone is 30 degrees.

For two items, say i and j which are in the area of importance of each other, there exists an inconsistency in the map if qi -pu > qj -pu , but rui > rui, or vice versa. We measure the quality of a PIM for user u with the number of inconsistencies and the mean value of error per inconsistency, defined as:

M Eu = 1 |E| i∈P IM (u) j∈Au(i) qi -pu qj -pu rui ruj ,
where |E| is the number of inconsistencies in the map and M E stands for Mean Error.

We compare the quality of maps generated with 5 methods com-EucEmbed Euclidean embedding in [START_REF] Khoshneshin | Collaborative filtering via euclidean embedding[END_REF] SVD-PCA SVD-like approach, projection with PCA Vis-PCA suggested visual predictor, projection with PCA SVD-CCA SVD-like approach, projection with CCA Vis-CCA suggested visual predictor, projection with CCA bining MF approaches with different projection techniques. Table 2 summarizes these methods. The prediction function suggested in [START_REF] Khoshneshin | Collaborative filtering via euclidean embedding[END_REF] is rui = µ + bu + bi -pu -qi 2 , where µ is the average rating of the dataset and bu and bi are user and item dependant variables respectively. The latter is indeed what leaves the door open for less relevant items to lie closer to a user than more relevant ones. We report the results on the Movielens 10 million ratings dataset.

The results for other datasets were similar. The map of each user contains the 5% of her total ratings corresponding to her test profile together with another 5% of known items shown to the user for the means of comparison (see Figure 3). Table 3 shows the results of the experiments for 10000 Movielens user maps. It is seen that the suggested visual predictor method has the fewest number of inconsistencies per user and the smallest mean error per inconsistency compared to other methods. The reason behind this quality is the special shape of our predictor function which is optimally coupled with the compromising property of CCA in preserving more important (short) distances. Furthermore, CCA always outperforms PCA in terms of average number of errors per user and mean error.

CONCLUSION

We studied visual representation of CF data. Our approach establishes an inverse relation between the relevance of data points and their distance in the Euclidean space. The projection method preserves the short distances and violates longer ones if tradeoff is inevitable. This results in a decrease in the number of those inconsistencies which are more likely to confuse the users. In this paper, we also presented an evaluation method for measuring the quality of recommendation maps. Our approach has fewer inconsistencies and smaller error compared to the maps generated using classical SVD-like approach. Usually, visualization techniques are likely to sacrifice precision for readability. This work presents a unified approach capitalizing on high precision of the MF approach with user-friendly representation of the results. Relating the correlation of data points to their distance in a high dimensional Euclidean space, our methodology provides a framework for using the existing projection techniques in the context of CF. Experiments on the three versions of the MovieLens dataset and the Netflix dataset show that the visual predictor has almost the same precision as the inner product predictor. The beauty of this approach is its capability in revealing latent information which are hard to understand even if one is disposed of the content information. Indeed, presented maps are the result of the collective wisdom of a huge number of users, sometimes being more promising than sniffing into tones of expert generated information. Our approach is also a solution to alleviate the explainability issues of MF. It is important for a recommender system to be able to explain the reason behind its recommendations. The neighborhood-based approach has the advantage of good explainability as it recommends based on the items/users already known to the active user. On the contrary, explaining the results of MF approach is more challenging, although this latter outperforms its neighborhood-based counterpart. The clustering property of visual maps and their distance interpretability are helpful in providing explanations and gaining the users' confidence. The running time of the MF approach is about half an hour on the Netflix dataset. Fortunately, the algorithm is run offline. It is recomputed with some frequency (for example daily or weekly). On the contrary, running times of the projection algorithm is very short. Consequently, it can be run on demand.

Figure 1 :

 1 Figure 1: The comparison between the suitability of the inner product and the Euclidean distance for visual prediction.

Figure 2 :

 2 Figure 2: RMSE of various approaches on different datasets.

  Improved visual predictor PIM projected from 20-dimensional latent feature space.

  SVD-like PIM projected from 10-dimensional latent feature space.

Figure 3 : 3 Figure 4 :

 334 Figure 3: PIM of an anonymous MovieLens user.

Table 1 :

 1 Properties of the datasets

		users	items	ratings	density%
	MovieLens100K	943	1682	100000	6.3
	MovieLens1M	6040	3883	1000209	4.24
	MovieLens	69878	10681	10000054	1.33
	Netflix	480189 17770 100480507	1.18

Table 2 :

 2 Recommendation methods for generation of visual recommendation maps.

		# of errors / user mean error
	EucEmbed	6.9219	1.9875
	SVD-PCA	7.4881	2.0239
	Vis-PCA	7.5500	2.1554
	SVD-CCA	7.0276	1.7050
	Vis-CCA	5.8013	1.5670

Table 3 :

 3 The quality of PIMs of different recommendation maps.

ACKNOWLEDEGMENTS

This work is supported partially by the ERC Starting Grant GOSS-PLE number 204742. It was started and partly conducted at INRIA Rennes Bretagne Atlantique where the author was a Ph.D. student. I am grateful to Prof. Anne-Marie Kermarrec and Dr. Claudia Ignat for all the support they devoted to this work.


t❤❛t ✐s t ∈ {1, 2

✸ ❊①✐st❡♥❝❡ ♦❢ t❤❡ ❙t❛t✐♦♥❛r② ❊q✉✐•✐❜r✐✉♠ ✐♥ ❆✈❡r❛❣❡✲r❡✇❛r❞ ❈❛s❡ ■♥ t❤❡ ♣r❡s❡♥t s❡❝t✐♦♥ ✇❡ ♣r❡s❡♥t ❛ r❡s✉•t ❛❜♦✉t t❤❡ ❡①✐st❡♥❝❡ ♦❢ st❛t✐♦♥❛r② ❡q✉✐•✐❜r✐✉♠ ✐♥ ❛♥♦♥②♠♦✉s s❡q✉❡♥t✐❛• ❣❛♠❡s ✇✐t❤ •♦♥❣✲t✐♠❡ ❛✈❡r❛❣❡ r❡✇❛r❞✳

❲❡ ♣r♦✈❡ ✐t ✉♥❞❡r t❤❡ ❢♦••♦✇✐♥❣ ❛ss✉♠♣t✐♦♥✿ ✭❆✶✮ ❚❤❡ s❡t ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ♦❢ ❛♥② ♣•❛②❡r S ❝❛♥ ❜❡ ♣❛rt✐t✐♦♥❡❞ ✐♥t♦ t✇♦ s❡ts S 0 ❛♥❞ S 1 s✉❝❤ t❤❛t ❢♦r ❡✈❡r② st❛t❡✲❛❝t✐♦♥ ❞✐str✐❜✉t✐♦♥ ♦❢ ❛•• t❤❡ ♦t❤❡r ♣•❛②❡rs τ ∈ ∆(S × A)✿ ✭❛✮ ❆•• t❤❡ st❛t❡s ❢r♦♠ S 0 ❛r❡ tr❛♥s✐❡♥t ✐♥ t❤❡ ▼❛r❦♦✈ ❝❤❛✐♥ ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ♦❢ ❛ ♣•❛②❡r ✉s✐♥❣ ❛♥② f ∈ U✳ ✭❜✮ ❚❤❡ s❡t S 1 ✐s str♦♥❣•② ❝♦♠♠✉♥✐❝❛t✐♥❣✳ ❚❤❡r❡ ❛r❡ ❛ ❝♦✉♣•❡ ♦❢ ❡q✉✐✈❛•❡♥t ❞❡✜♥✐t✐♦♥s ♦❢ ✏str♦♥❣•② ❝♦♠♠✉♥✐❝❛t✐♥❣✑ ♣r♦♣❡rt② ✉s❡❞ ❛❜♦✈❡ ❛♣♣❡❛r✐♥❣ ✐♥ t❤❡ •✐t❡r❛t✉r❡✳ ❲❡ ❢♦••♦✇ t❤❡ ♦♥❡ ❢♦r♠✉•❛t❡❞ ✐♥ ❬✸✶(✱ s❛②✐♥❣ t❤❛t ❛ s❡t S 1 ♦❢ st❛t❡s ✐♥ ❛ ▼❛r❦♦✈ ❉❡❝✐s✐♦♥ Pr♦❝❡ss ✐s str♦♥❣•② ❝♦♠♠✉♥✐❝❛t✐♥❣ ✐❢ t❤❡r❡ ❡①✐sts ❛ st❛t✐♦♥❛r② ♣♦•✐❝② ✸ f τ s✉❝❤ t❤❛t t❤❡ ♣r♦❜❛❜✐•✐t② ♦❢ ❣♦✐♥❣ ❢r♦♠ ❛♥② st❛t❡ s ∈ S 1 t♦ ❛♥② ♦t❤❡r s ′ ∈ S 1 ❢♦r ❛ ♣•
Q(a, τ ) =   1 -a+3p * 4 a 4 3p * 4 1 2 1 2 0 p * 2 0 1 -p * 2   , ✇❤❡r❡ p * = max{0, 1 -4τ 11 }. ✸ ◆♦t❡ t❤❛t ✇❡ ❛ss✉♠❡ t❤✐s st❛t✐♦♥❛r② ♣♦•✐❝② ♠❛② ❞❡♣❡♥❞ ♦♥ τ ✱ ❛s ✇❡ ❝♦♥s✐❞❡r t❤❡ ♣r♦♣❡r✲ t✐❡s ♦❢ t❤❡ ▼❛r❦♦✈ ❝❤❛✐♥ ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ♦❢ ❛ ♣•❛②❡r ✉♥❞❡r ✜①❡❞ st❛t❡✲❛❝t✐♦♥ ❞✐str✐❜✉t✐♦♥ ♦❢ ❛•• t❤❡ ♦t❤❡r ♣•❛②❡rs✳ ✹ ❆•• t❤❡ ♣r♦♣❡rt✐❡s ❛♣♣❡❛r✐♥❣ ✐♥ t❤❡ ❛ss✉♠♣t✐♦♥s ❛r❡ ❝♦♠♠♦♥•② ✉s❡❞ ✐♥ t❤❡ ▼❛r❦♦✈ ❞❡❝✐s✐♦♥ ♣r♦❝❡ss❡s •✐t❡r❛t✉r❡✳ ❚❤♦s❡ r❡❛❞❡rs ✇❤♦ ❛r❡ ♥♦t ❢❛♠✐•✐❛r ✇✐t❤ t❤❡♠ ♦r ❛r❡ ✐♥t❡r❡st❡❞ ✐♥ ♠✉t✉❛• r❡•❛t✐♦♥s❤✐♣s ❜❡t✇❡❡♥ t❤❡s❡ ♣r♦♣❡rt✐❡s ❛r❡ r❡❢❡rr❡❞ t♦ ❬✸✶✱✸✸(✳ ✺ ❚❤❡ ❡①❛♠♣•❡ ✐s ❛ r❡✇♦r❦✐♥❣ ♦❢ ❊①❛♠♣•❡ ✸✳ ✐♥ ❬✸✹(✳ ■t ✈✐♦•❛t❡s ❛ss✉♠♣t✐♦♥ ✭❆✶✮✱ ❛s ❡✳❣✳ ✇❤❡♥ τ 11 ≥ 1 4 ❢♦r t❤❡ ♣✉r❡ str❛t❡❣② ❛s✲ s✐❣♥✐♥❣ a = 0 ✐♥ st❛t❡ 1✱ st❛t❡s 1 ❛♥❞ 2 ❛r❡ ❛❜s♦r❜✐♥❣ ✐♥ t❤❡ ▼❛r❦♦✈ ❝❤❛✐♥ ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ♦❢ ❛ ♣•❛②❡r ❛♥❞ st❛t❡ 2 ✐s tr❛♥s✐❡♥t✱ ✇❤✐•❡ ✇❤❡♥ ✐t ❛ss✐❣♥s a = 1 st❛t❡s 1 ❛♥❞ 2 ❜❡❝♦♠❡ ❝♦♠♠✉♥✐❝❛t✐♥❣✳ ❲❡ ✇✐•• s❤♦✇ t❤❛t s✉❝❤ ❛ ❣❛♠❡ ❤❛s ♥♦ st❛t✐♦♥❛r② ❡q✉✐•✐❜r✐✉♠✳ ❙✉♣♣♦s❡ t❤❛t (f, µ * ) ✐s ❛♥ ❡q✉✐•✐❜r✐✉♠✳ ❲❡ ✇✐•• ❝♦♥s✐❞❡r t✇♦ ❝❛s❡s✿ ✭❛✮ τ 11 ≥ 1 4 ❢♦r τ ❝♦rr❡s♣♦♥❞✐♥❣ t♦ µ * ❛♥❞ f ✳ ❚❤❡♥ p * = 0✱ ❛♥❞ s♦ ✐❢ ❛ ♣
•❛②❡r ✉s❡s ❛❝t✐♦♥ 1 ✇✐t❤ ♣r♦❜❛❜✐•✐t② β✱ t❤❡ st❛t✐♦♥❛r② st❛t❡ ♦❢ t❤❡ ❝❤❛✐♥ ♦❢ ❤✐s st❛t❡s ✇❤❡♥ ❤✐s ✐♥✐t✐❛• st❛t❡✬s ❞✐str✐❜✉t✐♦♥ ✐s µ * ✐s 2(µ *

1 +µ * 2 ) 2+β , β(µ * 1 +µ * 2 ) 2+β , µ * 3 ❛♥❞ ❤✐s •♦♥❣✲t✐♠❡ ❛✈❡r❛❣❡ r❡✇❛r❞ ✐s (4 + β)(µ * 1 + µ * 2 ) 2 + β = 1 + 2 2 + β (µ * 1 + µ * 2 ), ✇❤✐❝❤ ✐s ❛ str✐❝t•② ❞❡❝r❡❛s✐♥❣ ❢✉♥❝t✐♦♥ ♦❢ β ✭r❡❝❛•• t❤❛t µ * 1 ≥ τ 11 ≥ 1 4 ✮✳ ❚❤✉s ❤✐s ❜❡st r❡s♣♦♥s❡ t♦ f ✐s t❤❡ ♣♦•✐❝② ✇❤✐❝❤ ❛ss✐❣♥s ♣r♦❜❛❜✐•✐t② 1 t♦ ❛❝t✐♦♥ a = 0 ✐♥ st❛t❡ 1✳ ❇✉t ✐❢ ❛•• t❤❡ ♣•❛②❡rs ✉s❡ s✉❝❤ ♣♦•✐❝②✱ τ 11 = 0✱ ✇❤✐❝❤ ❝♦♥tr❛❞✐❝ts ♦✉r ❛ss✉♠♣t✐♦♥ t❤❛t ✐t ✐s ♥♦ •❡ss t❤❛♥ 1 4 ✳ ✭❜✮ τ 11 < 1 4 ✳ ❚❤❡♥ ✐t ❝❛♥ ❜❡ ❡❛s✐•② s❡❡♥ t❤❛t t❤❡ st❛t✐♦♥❛r② st❛t❡ ♦❢ ❛♥② ♣•❛②❡r✬s ❝❤❛✐♥ ✇❤❡♥ ❤❡ ✉s❡s ❛❝t✐♦♥ 1 ✇✐t❤ ♣r♦❜❛❜✐•✐t② β ∈ [0, 1] ✐s ✐♥❞❡♣❡♥❞❡♥t ♦❢ t❤❡ ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ ♦❢ ❤✐s st❛t❡ µ * ❛♥❞ ❡q✉❛• t♦ 2 5+β , β 5+β , 3 5+β ✱ ✇❤✐❝❤ ❣✐✈❡s ❤✐♠ t❤❡ r❡✇❛r❞ ♦❢ 4+β 5+β = 1 -1 5+β ✱ ✇❤✐❝❤ ✐s ❝•❡❛r•② ❛ str✐❝t•② ✐♥❝r❡❛s✐♥❣ ❢✉♥❝t✐♦♥ ♦❢ β✳ ❚❤✉s t❤❡ ❜❡st r❡s♣♦♥s❡ t♦ f ✐s t♦ ♣•❛② ❛❝t✐♦♥ a = 1 ✇✐t❤ ♣r♦❜❛❜✐•✐t② 1✱ ✇❤✐❝❤✱ ✐❢ ❛♣♣•✐❡❞ ❜② ❛•• t❤❡ ♣•❛②❡rs✱ r❡s✉•ts ✐♥ st❛t✐♦♥❛r② st❛t❡ µ * = 1 3 , 1 6 , 1 2 ❛♥❞ ❝♦♥s❡q✉❡♥t•② τ 11 = 1 3 ✱ ❝♦♥tr❛❞✐❝t✐♥❣ t❤❡ ❛ss✉♠♣t✐♦♥ t❤❛t ✐t ✐s •❡ss t❤❛♥ 1 4 ✳ ❚❤✉s t❤✐s ❣❛♠❡ ❝❛♥♥♦t ❤❛✈❡ ❛ st❛t✐♦♥❛r② ❡q✉✐•✐❜r✐✉♠✳ ◆♦✇ ✇❡ ❛r❡ r❡❛❞② t♦ ❢♦r♠✉•❛t❡ t❤❡ ♠❛✐♥ r❡s✉•t ♦❢ t❤✐s s❡❝t✐♦♥✳ ❚❤❡♦r❡♠ ✶ ❊✈❡r② ❛♥♦♥②♠♦✉s s❡q✉❡♥t✐❛• ❣❛♠❡ ✇✐t❤ •♦♥❣✲t✐♠❡ ❛✈❡r❛❣❡ ♣❛②♦✛ s❛t✐s❢②✐♥❣ ✭❆✶✮ ❤❛s ❛ st❛t✐♦♥❛r② ❡q✉✐•✐❜r✐✉♠✳ ❇❡❢♦r❡ ✇❡ ♣r♦✈❡ t❤❡ t❤❡♦r❡♠ •❡t ✉s ✐♥tr♦❞✉❝❡ s♦♠❡ ❛❞❞✐t✐♦♥❛• ♥♦t❛t✐♦♥✳ ❲❡ ✇✐•• ❝♦♥s✐❞❡r ❛ ▼❛r❦♦✈ ❞❡❝✐s✐♦♥ ♣r♦❝❡ss M(τ ) ♦❢ ❛♥ ✐♥❞✐✈✐❞✉❛• ❢❛❝❡❞ ✇✐t❤ ❛ ✜①❡❞ ✭♦✈❡r t✐♠❡✮ ❞✐str✐❜✉t✐♦♥ ♦❢ st❛t❡✲❛❝t✐♦♥ ♣❛✐rs ♦❢ ❛•• t❤❡ ♦t❤❡r ♣•❛②❡rs✳ ❋♦r t❤✐s ✜①❡❞ τ ∈ ∆(S × A) •❡t J τ (f, µ) ❞❡♥♦t❡ t❤❡ •♦♥❣✲t✐♠❡ ❛✈❡r❛❣❡ ♣❛②♦✛ ✐♥ t❤✐s ♣r♦❝❡ss ✇❤❡♥ t❤❡ ♣•❛②❡r ✉s❡s st❛t✐♦♥❛r② ♣♦•✐❝② f ❛♥❞ t❤❡ ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ ♦❢ st❛t❡s ✐s µ✱ t❤❛t ✐s J τ (f, µ) = lim sup T →∞ 1 T E µ,Q,f T t=1 u(s t , a t , τ ). ❇② ✇❡•• ❦♥♦✇♥ r❡s✉•ts ❢r♦♠ ❞②♥❛♠✐❝ ♣r♦❣r❛♠♠✐♥❣ ✭s❡❡ ❡✳❣✳ ❬✸✷(✮✱ ✐♥ ❛ ✇❡❛❦•② ❝♦♠♠✉♥✐❝❛t✐♥❣ ▼❛r❦♦✈ ❞❡❝✐s✐♦♥ ♣r♦❝❡ss ✭t❤✐s ✐s s✉❝❤ ❛ ♣r♦❝❡ss ❜② ✭❆✶✮✮ t❤❡ ♦♣t✐♠❛• ❣❛✐♥ ✐s ✐♥❞❡♣❡♥❞❡♥t ♦❢ µ✳ ❲❡ ❞❡♥♦t❡ t❤✐s ✉♥✐❢♦r♠ ♦♣t✐♠❛• ❣❛✐♥ ❜② G(τ )✱ t❤❛t ✐s G(τ ) = sup f :S→A J τ (f, µ) ❢♦r ❛♥② ✜①❡❞ µ ∈ ∆(S). ▲❡♠♠❛ ✷ st❛t❡s ❛ ❝r✉❝✐❛• ❢❡❛t✉r❡ ♦❢ G✳ ■t ✐s ♣r❡❝❡❞❡❞ ❜② ❛♥♦t❤❡r t❡❝❤♥✐❝❛• ♦♥❡✳ ▲❡♠♠❛ ✶ ❙✉♣♣♦s❡ t❤❛t µ(n) ❛r❡ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡s ♦❢ ▼❛r❦♦✈ ❝❤❛✐♥s ✇✐t❤ ✜✲ ♥✐t❡ st❛t❡ s❡t S ❛♥❞ ✇✐t❤ tr❛♥s✐t✐♦♥ ♠❛tr✐❝❡s P (n) r❡s♣❡❝t✐✈❡•②✳ ❚❤❡♥ ✐❢ µ(n) → µ ❛♥❞ P (n) → P ✱ t❤❡♥ µ ✐s ❛♥ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ❢♦r t❤❡ ▼❛r❦♦✈ ❝❤❛✐♥ ✇✐t❤ tr❛♥s✐t✐♦♥ ♠❛tr✐① P ✳ Pr♦♦❢✿ ❇② t❤❡ ❞❡✜♥✐t✐♦♥ ♦❢ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ❡✈❡r② µ(n) s❛t✐s✜❡s ❢♦r ❡✈❡r② s ∈ S (µ(n)) s = i∈S (µ(n)) i (P (n)) si . ■❢ ✇❡ ♣❛ss t♦ t❤❡ •✐♠✐t✱ ✇❡ ♦❜t❛✐♥ µ s = i∈S µ i P si ., ✇❤✐❝❤ ♠❡❛♥s t❤❛t µ ✐s ❛♥ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ❢♦r t❤❡ ▼❛r❦♦✈ ❝❤❛✐♥ ✇✐t❤ tr❛♥✲ s✐t✐♦♥ ♠❛tr✐① P ✳ ▲❡♠♠❛ ✷ ❯♥❞❡r ✭❆✶✮ G ✐s ❛ ❝♦♥t✐♥✉♦✉s ❢✉♥❝t✐♦♥ ♦❢ τ ✳ Pr♦♦❢✿ ▲❡t τ n ❜❡ ❛ s❡q✉❡♥❝❡ ♦❢ ♣r♦❜❛❜✐•✐t② ♠❡❛s✉r❡s ♦♥ S × A ❝♦♥✈❡r❣✐♥❣ t♦ τ ✳ ❙✐♥❝❡ ❛•• ♦❢ t❤❡ ▼❉Ps ✇❡ ❝♦♥s✐❞❡r ❤❡r❡ ❤❛✈❡ ✜♥✐t❡ st❛t❡ s♣❛❝❡✱ ❡❛❝❤ ♦❢ t❤❡♠ ❤❛s ❛ st❛t✐♦♥❛r② ♦♣t✐♠❛• ♣♦•✐❝② ✻ ✱ s❛② ♣♦•✐❝② f n ✐s ♦♣t✐♠❛• ✐♥ M(τ n )✳ ◆❡①t✱ •❡t µ n ❜❡ ❛♥ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ❝♦rr❡s♣♦♥❞✐♥❣ t♦ str❛t❡❣② f n ✐♥ M(τ n ) ✭❜② ✭❆✶✮ s✉❝❤ ❛ ♠❡❛s✉r❡ ❡①✐sts✱ ♠❛②❜❡ ♠♦r❡ t❤❛♥ ♦♥❡✮✳ ❙✉❝❤ ❛♥ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ♠✉st s❛t✐s❢② G(τ n ) = s∈S a∈A (f n (s)) a µ n s u(s, a, τ n ), ✭✶✮ ♦t❤❡r✇✐s❡ f n ✇♦✉•❞ ♥♦t ❜❡ ♦♣t✐♠❛•✳ ◆♦t❡ ♥❡①t t❤❛t U ❛♥❞ ∆(S) ❛r❡ ❝♦♠♣❛❝t s❡ts✳ ❚❤✉s t❤❡r❡ ❡①✐sts ❛ s✉❜✲ s❡q✉❡♥❝❡ ♦❢ f n ❝♦♥✈❡r❣✐♥❣ t♦ s♦♠❡ f 0 ∈ U ❛♥❞ t❤❡♥ ❛ s✉❜s❡q✉❡♥❝❡ ♦❢ µ n ❝♦♥✈❡r❣✐♥❣ t♦ s♦♠❡ µ 0 ✳ ❲✐t❤♦✉t ❛ •♦ss ♦❢ ❣❡♥❡r❛•✐t② ✇❡ ♠❛② ❛ss✉♠❡ t❤❛t t❤❡s❡ ❛r❡ s❡q✉❡♥❝❡s f n ❛♥❞ µ n t❤❛t ❛r❡ ❝♦♥✈❡r❣❡♥t✳ ❇② t❤❡ ❝♦♥t✐♥✉✐t② ❛ss✉♠♣t✐♦♥ ❛❜♦✉t Q ❛♥❞ ▲❡♠♠❛ ✶✱ µ 0 ✐s ❛♥ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ❝♦rr❡s♣♦♥❞✐♥❣ t♦ f 0 ✐♥ M(τ )✳ ■❢ ✇❡ ♥❡①t ♣❛ss t♦ t❤❡ •✐♠✐t ✐♥ ✭✶✮ ✇❡ ❣❡t lim n→∞ G(τ n ) = s∈S a∈A (f 0 (s)) a µ 0 s u(s, a, τ ) = J τ (f 0 , µ 0 ). ❇✉t t❤✐s ✐♠♣•✐❡s t❤❛t G(τ ) ≥ lim n→∞ G(τ n )✳ ✻ ❖❢ ❝♦✉rs❡ ❛ st❛t✐♦♥❛r② ♣♦•✐❝② ✐s ♦♥•② ❛ ❢✉♥❝t✐♦♥ ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡ s ❤❡r❡✳ ❚♦ s❤♦✇ t❤❡ ✐♥✈❡rs❡ ✐♥❡q✉❛•✐t②✱ s✉♣♣♦s❡ t❤❛t f ∈ U ✐s ❛♥ ♦♣t✐♠❛• ♣♦•✐❝② ✐♥ M(τ )✳ ❇② ✭❆✶✮ t❤❡ st❛t❡s ✐♥ t❤❡ ▼❛r❦♦✈ ❝❤❛✐♥ ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ❢♦r ❛ ✉s❡r ❛♣♣•②✐♥❣ f ✐♥ M(τ ) ❝❛♥ ❜❡ ❞✐✈✐❞❡❞ ✐♥t♦ ❛ ❝•❛ss ♦❢ tr❛♥s✐❡♥t st❛t❡s ❛♥❞ ❛ ♥✉♠❜❡r ♦❢ ❝♦♠♠✉♥✐❝❛t✐♥❣ ❝•❛ss❡s✳ ▲❡t S * ❜❡ ❛ ❝♦♠♠✉♥✐❝❛t✐♥❣ ❝•❛ss s✉❝❤ t❤❛t t❤❡ ❡r❣♦❞✐❝ ♣❛②♦✛ ✐♥ t❤✐s ❝•❛ss ✐s ❡q✉❛• t♦ G(τ )✳ ❉❡✜♥❡ ♥♦✇ t❤❡ ♣♦•✐❝✐❡s g n ✐♥ t❤❡ ❢♦••♦✇✐♥❣ ✇❛②✿ g n (s) = f (s) ✇❤❡♥ s ∈ S * f τ n (s) ✇❤❡♥ s ∈ S \ S * ✭❍❡r❡ f τ n ✐s ❛ ❝♦♠♠✉♥✐❝❛t✐♥❣ ♣♦•✐❝② ❞❡r✐✈❡❞ ❢r♦♠ ❛ss✉♠♣t✐♦♥ ✭❆✶✮✮✳ ❖♥❡ ❝❛♥ ❡❛s✐•② ♥♦t✐❝❡ t❤❛t ✉♥❞❡r t❤❡s❡ ♣♦•✐❝✐❡s ❛♣♣•✐❡❞ ✐♥ M(τ n )✱ ❛•• t❤❡ st❛t❡s ❢r♦♠ S \ S * ✇♦✉•❞ ❜❡ tr❛♥s✐❡♥t✳ ◆♦✇ •❡t µ n ❜❡ ❛♥ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ❝♦rr❡s♣♦♥❞✐♥❣ t♦ g n ✐♥ M(τ n )✳ ❆❣❛✐♥ ✉s✐♥❣ ▲❡♠♠❛ ✶ ✇❡ ❝❛♥ s❤♦✇ t❤❛t t❤❡ •✐♠✐t ✭♣♦ss✐❜•② ♦✈❡r ❛ s✉❜s❡q✉❡♥❝❡✮ ♦❢ t❤❡ s❡q✉❡♥❝❡ µ n ✱ s❛② µ 0 ✐s ❛♥ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ♦❢ t❤❡ •✐♠✐t ♦❢ g n ✱ ✇❤✐❝❤ ✐s ❡q✉❛• t♦ f ♦♥ S * ✳ ❆t t❤❡ s❛♠❡ t✐♠❡ µ 0 s = 0 ❢♦r s ∈ S \ S * ✱ s♦ ✇❡ ❝❛♥ ✇r✐t❡ ✭❢r♦♠ t❤❡ ❞❡✜♥✐t✐♦♥ ♦❢ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡✮ ❢♦r ❡✈❡r② s ∈ S * ✿ µ 0 s = i∈S a∈A Q(s|i, a, τ )(g 0 (i)) a µ 0 i = i∈S * a∈A Q(s|i, a, τ )(g 0 (i)) a µ 0 i = i∈S * a∈A Q(s|i, a, τ )(f (i)) a µ 0 i = i∈S a∈A Q(s|i, a, τ )(f (i)) a µ 0 i , ✇❤✐❝❤ ♠❡❛♥s t❤❛t µ 0 ✐s ❛•s♦ ❛♥ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ❢♦r f ❛♥❞ ✐t ✐s ❡♥t✐r❡•② ❝♦♥❝❡♥tr❛t❡❞ ♦♥ S * ✳ ❇✉t s✐♥❝❡ S * ✐s ❛ ❝♦♠♠✉♥✐❝❛t✐♥❣ ❝•❛ss ✉♥❞❡r f ✱ t❤✐s ✐♠♣•✐❡s J τ (g 0 , µ 0 ) = J τ (f, µ 0 ) = G(τ ). ❖♥ t❤❡ ♦t❤❡r ❤❛♥❞ J τ (g 0 , µ 0 ) = s∈S a∈A (g 0 (s)) a µ 0 s u(s, a, τ ) = lim n→∞ s∈S a∈A (g n (s)) a µ n s u(s, a, τ n ) = lim n→∞ J τ n (g n , µ n ) ≤ lim n→∞ G(τ n ), ❡♥❞✐♥❣ t❤❡ ♣r♦♦❢✳ Pr♦♦❢ ♦❢ ❚❤❡♦r❡♠ ✶✿ ❲❡ ❝♦♥s✐❞❡r t✇♦ ♠✉•t✐❢✉♥❝t✐♦♥s ♦❢ τ ∈ ∆(S × A)✿ B(τ ) := ρ ∈ ∆(S × A) : s∈S a∈A ρ sa u(s, a, τ ) = G(τ ) ✭✷✮ C(τ ) = ρ ∈ ∆(S × A) : a∈A ρ sa = x∈S b∈B Q(s|x, b, τ )ρ xb ✭✸✮ ❛♥❞ •❡t Ψ (τ ) := B(τ ) ∩ C(τ )✳ ❲❡ ✇✐•• s❤♦✇ t❤❛t Ψ ❤❛s ❛ ✜①❡❞ ♣♦✐♥t✱ ❛♥❞ t❤❡♥ t❤❛t t❤✐s ✜①❡❞ ♣♦✐♥t ❝♦rr❡s♣♦♥❞s t♦ ❛♥ ❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ ❣❛♠❡✳ ❋✐rst ♥♦t❡ t❤❛t C(τ ) ✐s t❤❡ s❡t ♦❢ ❛•• t❤❡ ♣♦ss✐❜•❡ st❛t✐♦♥❛r② st❛t❡✲❛❝t✐♦♥ ♠❡❛s✉r❡s ✐♥ M(τ )✳ ❇② ❚❤❡♦r❡♠ ✶ ✐♥ ❬✸✺( ✐t ✐s ❛•s♦ t❤❡ s❡t ♦❢ ♦❝❝✉♣❛t✐♦♥ ♠❡❛✲ s✉r❡s ❝♦rr❡s♣♦♥❞✐♥❣ t♦ ❛•• t❤❡ ♣♦ss✐❜•❡ st❛t✐♦♥❛r② ♣♦•✐❝✐❡s ❛♥❞ ❛•• t❤❡ ♣♦ss✐❜•❡ ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥s ♦❢ st❛t❡s ✐♥ M(τ )✳ ❙✐♥❝❡ G(τ ) ✐s t❤❡ ♦♣t✐♠❛• r❡✇❛r❞ ✐♥ t❤✐s ▼❉P✱ t❤❡r❡ ❡①✐sts ❛ st❛t✐♦♥❛r② ♣♦•✐❝②✱ ❛♥❞ t❤✉s ❛♥ ♦❝❝✉♣❛t✐♦♥ ♠❡❛s✉r❡ ❝♦rr❡s♣♦♥❞✐♥❣ t♦ ✐t✱ ❢♦r ✇❤✐❝❤ t❤❡ r❡✇❛r❞ ✐s ❡q✉❛• t♦ G(τ )✳ ❚❤✐s ✐♠♣•✐❡s t❤❛t ❢♦r ❛♥② τ ✱ Ψ (τ ) ✐s ♥♦♥❡♠♣t②✳ ❋✉rt❤❡r ♥♦t❡ t❤❛t ❢♦r ❛♥② τ ❜♦t❤ B(τ ) ❛♥❞ C(τ ) ❛r❡ tr✐✈✐❛••② ❝♦♥✈❡①✱ ❛♥❞ t❤✉s s♦ ✐s t❤❡✐r ✐♥t❡rs❡❝t✐♦♥✳ ❋✐♥❛••②✱ ❛s ❛♥ ✐♠♠❡❞✐✲ ❛t❡ ❝♦♥s❡q✉❡♥❝❡ ♦❢ ▲❡♠♠❛ ✶✱ C ❤❛s ❛ ❝•♦s❡❞ ❣r❛♣❤✳ ❖♥ t❤❡ ♦t❤❡r ❤❛♥❞ t❤❡ ❝•♦s❡❞♥❡ss ♦❢ t❤❡ ❣r❛♣❤ ♦❢ B ✐s ❛ tr✐✈✐❛• ❝♦♥s❡q✉❡♥❝❡ ♦❢ t❤❡ ❝♦♥t✐♥✉✐t② ♦❢ u ✭❜② ❛ss✉♠♣t✐♦♥✮ ❛♥❞ G ✭❜② ▲❡♠♠❛ ✷✮✳ ❚❤❡ ❣r❛♣❤ ♦❢ Ψ ✐s t❤❡ ✐♥t❡rs❡❝t✐♦♥ ♦❢ t❤❡ t✇♦ ❛♥❞ t❤✉s ✐s ❛•s♦ ❝•♦s❡❞✳ ❚❤❡ ❡①✐st❡♥❝❡ ♦❢ ❛ ✜①❡❞ ♣♦✐♥t ♦❢ Ψ ❢♦••♦✇s ♥♦✇ ❢r♦♠ ••✐❝❦❜❡r❣✬s ✜①❡❞ ♣♦✐♥t t❤❡♦r❡♠ ❬✸✻(✳ ◆♦✇ s✉♣♣♦s❡ τ * ✐s t❤✐s ✜①❡❞ ♣♦✐♥t✳ ❙✐♥❝❡ ✐t ✐s ❛ ✜①❡❞ ♣♦✐♥t ♦❢ C✱ ✐t s❛t✐s✜❡s✿ a∈A τ * sa = x∈S b∈B Q(s|x, b, τ * )τ * xb = Φ(s|τ * ). ❚❤✐s ✐♠♣•✐❡s t❤❛t ✐❢ t❤❡ ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ ♦❢ st❛t❡s ✐s τ * S ❛♥❞ ♣•❛②❡rs ❛♣♣•② st❛t✐♦♥❛r② ♣♦•✐❝② f ❞❡✜♥❡❞ ❢♦r ❛♥② τ ∈ ∆(S × A) ❜② ✼ ✿ (f (s), τ ) a = τ * sa b∈A τ * sa ✐❢ b∈A τ * sa > 0 δ[a 0 ] ♦t❤❡r✇✐s❡ ✭✹✮ ❢♦r ❛♥② ✜①❡❞ a 0 ∈ A✱ t❤❡ ❞✐str✐❜✉t✐♦♥ ♦❢ st❛t❡✲❛❝t✐♦♥ ♣❛✐rs ✐♥ t❤❡ ♣♦♣✉•❛t✐♦♥ ✐s ❛•✇❛②s τ * ✳ ❖♥ t❤❡ ♦t❤❡r ❤❛♥❞✱ s✐♥❝❡ τ * ∈ B(τ * )✱ f ✐s t❤❡ ❜❡st r❡s♣♦♥s❡ ♦❢ ❛ ♣•❛②❡r ✇❤❡♥ t❤❡ st❛t❡✲❛❝t✐♦♥ ❞✐str✐❜✉t✐♦♥ ✐s ❛•✇❛②s τ * ✱ ❛♥❞ t❤✉s t♦❣❡t❤❡r ✇✐t❤ τ * S ❛♥ ❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ ❣❛♠❡✳ ✹ ❊①✐st❡♥❝❡ ♦❢ t❤❡ ❙t❛t✐♦♥❛r② ❊q✉✐•✐❜r✐✉♠ ✐♥ ❚♦t❛•✲r❡✇❛r❞ ❈❛s❡ ■♥ t❤✐s s❡❝t✐♦♥ ✇❡ s❤♦✇ t❤❛t ❛•s♦ ❢♦r t❤❡ t♦t❛• r❡✇❛r❞ ❝❛s❡ ✉♥❞❡r s♦♠❡ ❢❛✐r•② ♠✐•❞ ❛ss✉♠♣t✐♦♥s t❤❡ ❣❛♠❡ ❤❛s ❛♥ ❡q✉✐•✐❜r✐✉♠✳ ❲❤❛t ✇❡ ✇✐•• ❛ss✉♠❡ ✐s t❤❡ ❢♦••♦✇✐♥❣✿ ✭❚✶✮ ❚❤❡r❡ ❡①✐sts ❛ p 0 > 0 s✉❝❤ t❤❛t ❢♦r ❛♥② ✜①❡❞ st❛t❡✲❛❝t✐♦♥ ♠❡❛s✉r❡ τ ❛♥❞ ✉♥❞❡r ❛♥② st❛t✐♦♥❛r② ♣♦•✐❝② f t❤❡ ♣r♦❜❛❜✐•✐t② ♦❢ ❣❡tt✐♥❣ ❢r♦♠ ❛♥② st❛t❡ s ∈ S \ {s 0 } t♦ s 0 ✐♥ |S| -1 st❡♣s ✐s ♥♦t s♠❛••❡r t❤❛♥ p 0 ✳ ❲❡ ✇r✐t❡ t❤❛t t❤✐s ❛ss✉♠♣t✐♦♥ ✐s ❢❛✐r•② ♠✐•❞✱ ❛s ✐t ✐s ♥♦t ♦♥•② ♥❡❝❡ss❛r② ❢♦r ♦✉r t❤❡♦r❡♠ t♦ ❤♦•❞✱ ❜✉t ❛•s♦ ❢♦r t❤❡ t♦t❛• ❝♦st ♠♦❞❡• t♦ ♠❛❦❡ s❡♥s❡✱ ❛s ✐t ✐s tr✐✈✐❛••② s❤♦✇♥ ✐♥ ❛♥ ❡①❛♠♣•❡ ❜❡•♦✇✿ ❊①❛♠♣•❡ ✷ ❈♦♥s✐❞❡r ❛♥ ❛♥♦♥②♠♦✉s s❡q✉❡♥t✐❛• ❣❛♠❡ ✇✐t❤ t♦t❛• ❝♦st ✇✐t❤ S = {1, 2, 3} ✭❛♥❞ st❛t❡ s 0 ❞❡♥♦t❡❞ ❤❡r❡ ❛s s = 0✮ ❛♥❞ A(s, µ) = {1, 2}, ✐❢ s = 1 {1}, ♦t❤❡r✇✐s❡ ✳ ✼ ❍❡r❡ ❛♥❞ ✐♥ t❤❡ s❡q✉❡• δ[x] ❞❡♥♦t❡s ❛ ♣r♦❜❛❜✐•✐t② ♠❡❛s✉r❡ ❝♦♥❝❡♥tr❛t❡❞ ✐♥ x✳ ❚❤❡ ✐♠♠❡❞✐❛t❡ r❡✇❛r❞s ❢♦r t❤❡ ♣•❛②❡rs ❞❡♣❡♥❞ ♦♥•② ♦♥ t❤❡✐r ♣r✐✈❛t❡ st❛t❡ ❛s ❢♦••♦✇s✿ u(s) = 1, ✐❢ s = 1 -1, ♦t❤❡r✇✐s❡ ✳ ❋✐♥❛••②✱ t❤❡ tr❛♥s✐t✐♦♥s ♦❢ t❤❡ ▼❛r❦♦✈ ❝❤❛✐♥ ♦❢ ♣r✐✈❛t❡ st❛t❡s ♦❢ ❡❛❝❤ ♣•❛②❡r ❛r❡ ❞❡✜♥❡❞ ❛s ❢♦••♦✇s✿ ✐❢ ❤✐s ❛❝t✐♦♥ ✐♥ st❛t❡ 1 ✐s 1✱ ❤❡ ♠♦✈❡s ✇✐t❤ ♣r♦❜❛❜✐•✐t② 1 t♦ st❛t❡ 2❀ ✐❢ ❤✐s ❛❝t✐♦♥ ✐s 2✱ ❤❡ ♠♦✈❡s ✇✐t❤ ♣r♦❜❛❜✐•✐t② 1 t♦ st❛t❡ 3✳ ■♥ st❛t❡ 2 ❤❡ ♠♦✈❡s t♦ 1 ✇✐t❤ ♣r♦❜❛❜✐•✐t② 1✱ ✇❤✐•❡ ✐♥ st❛t❡ 3 ❤❡ ❞✐❡s ✇✐t❤ ♣r♦❜❛❜✐•✐t② 1 2 ❛♥❞ st❛②s ✐♥ 3 ✇✐t❤ ♣r♦❜❛❜✐•✐t② 1 2 ✳ ❚❤✐s ❣❛♠❡ ✐s ❝♦♠♣•❡t❡•② ❞❡❝♦✉♣•❡❞ ✭✐♥ t❤❡ s❡♥s❡ t❤❛t ♥❡✐t❤❡r t❤❡ r❡✇❛r❞s ♥♦r t❤❡ tr❛♥s✐t✐♦♥s ♦❢ ❛♥② ♣•❛②❡r ❞❡♣❡♥❞ ♦♥ t❤♦s❡ ♦❢ t❤❡ ♦t❤❡rs✮✱ s♦ ✐t ✐s ❡❛s② t♦ ❛♥❛•②③❡✳ ■t ✐s ✐♠♠❡❞✐❛t❡ t♦ s❡❡ t❤❛t ✉♥❞❡r ♣✉r❡ st❛t✐♦♥❛r② ♣♦•✐❝② ❝❤♦♦s✐♥❣ ❛❝t✐♦♥ 1 ✐♥ st❛t❡ 1 ❛ ♣•❛②❡r ♥❡✈❡r ❞✐❡s✳ ▼♦r❡♦✈❡r✱ ❤❡ r❡❝❡✐✈❡s ♣❛②♦✛s ♦❢ 1 ❛♥❞ -1 ✐♥ s✉❜s❡q✉❡♥t ♣❡r✐♦❞s✱ s♦ ❤✐s r❡✇❛r❞ ✭t❤❡ s✉♠ ♦❢ t❤❡s❡ r❡✇❛r❞s ♦✈❡r ❤✐s •✐❢❡t✐♠❡✮ ✐s ♥♦t ✇❡•• ❞❡✜♥❡❞✳ ■❢ ✇❡ tr② t♦ ❝♦rr❡❝t ✐t ❜② ❞❡✜♥✐♥❣ t❤❡ t♦t❛• r❡✇❛r❞ ❛s t❤❡ lim sup ♦r lim inf ♦❢ ❤✐s ❛❝❝✉♠✉•❛t❡❞ r❡✇❛r❞s ❛❢t❡r n ♣❡r✐♦❞s ♦❢ ❤✐s •✐❢❡✱ ✇❡ ♦❜t❛✐♥ ❛ str❛♥❣❡ s✐t✉❛t✐♦♥ t❤❛t t❤❡ ♣♦•✐❝② ❝❤♦♦s✐♥❣ ❛❝t✐♦♥ 1 ✐s ♦♣t✐♠❛• ❢♦r ❡❛❝❤ ♦❢ t❤❡ ♣•❛②❡rs ✐♥ t❤❡ lim sup ✈❡rs✐♦♥ ♦❢ t❤❡ r❡✇❛r❞✱ ❛♥❞ ❤✐s ✇♦rst ♣♦ss✐❜•❡ ♣♦•✐❝② ❢♦r t❤❡ lim inf ✈❡rs✐♦♥✳ |❡♠❛r❦ ✷ ❚❤❡ t♦t❛• r❡✇❛r❞ ♠♦❞❡•✱ s♣❡❝✐✜❝❛••② ✇❤❡♥ ✭❚✶✮ ✐s ❛ss✉♠❡❞✱ ❜❡❛rs ❛ •♦t ♦❢ r❡s❡♠❜•❛♥❝❡ t♦ ❛♥ ❡①♣♦♥❡♥t✐❛••② ❞✐s❝♦✉♥t❡❞ ♠♦❞❡• ✇❤❡r❡ t❤❡ ❞✐s❝♦✉♥t ❢❛❝t♦r ✐s ❛••♦✇❡❞ t♦ ✢✉❝t✉❛t❡ ♦✈❡r t✐♠❡✱ ✇❤✐❝❤ s✉❣❣❡sts t❤❛t t❤❡ r❡s✉•ts ✐♥ t❤❡ t✇♦ ♠♦❞❡•s s❤♦✉•❞ ♥♦t ❞✐✛❡r ♠✉❝❤✳ ◆♦t❡ ❤♦✇❡✈❡r t❤❛t t❤❡r❡ ✐s ♦♥❡ ❡ss❡♥t✐❛• ❞✐✛❡r❡♥❝❡ ❜❡t✇❡❡♥ t❤❡s❡ t✇♦ ♠♦❞❡•s✳ ❚❤❡ ❵❞✐s❝♦✉♥t ❢❛❝t♦r✬ ✐♥ t❤❡ t♦t❛• r❡✇❛r❞ ♠♦❞❡• ✭✇❤✐❝❤ ✐s t❤❡ r❛t✐♦ ♦❢ t❤♦s❡ ✇❤♦ st❛② ❛•✐✈❡ ❛❢t❡r ❛ ❣✐✈❡♥ ♣❡r✐♦❞ t♦ t❤♦s❡ ✇❤♦ ✇❡r❡ ❛•✐✈❡ ❛t ✐ts ❜❡❣✐♥♥✐♥❣✮ ❛♣♣❡❛rs ♥♦t ♦♥•② ✐♥ t❤❡ ❝✉♠✉•❛t✐✈❡ r❡✇❛r❞ ♦❢ t❤❡ ♣•❛②❡rs ❜✉t ❛•s♦ ✐♥ t❤❡ st❛t✐♦♥❛r② st❛t❡ ♦❢ t❤❡ ❣❛♠❡✱ ❛♥❞ t❤✉s ❛•s♦ ✐♥ t❤❡ ♣❡r✲♣❡r✐♦❞ r❡✇❛r❞s ♦❢ t❤❡ ♣•❛②❡rs✳ ❚❤✉s t❤✐s ✐s ❛♥ ❡ss❡♥t✐❛••② ❞✐✛❡r❡♥t ✭❛♥❞ s•✐❣❤t•② ♠♦r❡ ❝♦♠♣•❡①✮ ♣r♦❜•❡♠✳ ❖♥ t❤❡ ♦t❤❡r ❤❛♥❞✱ t❤❡ ❢❛❝t t❤❛t ❡❛❝❤ ♦❢ t❤❡ ♣•❛②❡rs •✐✈❡s ❢♦r ❛ ✜♥✐t❡ ♣❡r✐♦❞ ❛♥❞ t❤❡♥ ✐s r❡♣•❛❝❡❞ ❜② ❛♥♦t❤❡r ♣•❛②❡r✱ ✇✐t❤ ❛ ✜①❡❞ ❢r❛❝t✐♦♥ ♦❢ ♣•❛②❡rs ❞❡❛❞ ❛♥❞ ✜①❡❞ ❢r❛❝t✐♦♥s ♦❢ ♣•❛②❡rs ✐♥ ❡❛❝❤ ♦❢ t❤❡ st❛t❡s ✇❤❡♥ t❤❡ ❣❛♠❡ ✐s ✐♥ ❛ st❛t✐♦♥❛r② st❛t❡✱ ♠❛❦❡s t❤✐s ♠♦❞❡• s✐♠✐•✐❛r t♦ t❤❡ ❛✈❡r❛❣❡ r❡✇❛r❞ ♦♥❡✳ ■♥ ❢❛❝t✱ ✉s✐♥❣ t❤❡ r❡♥❡✇❛• t❤❡♦r❡♠✱ ✇❡ ❝❛♥ r❡•❛t❡ t❤❡ r❡✇❛r❞s ♦❢ t❤❡ ♣•❛②❡rs ✐♥ t❤❡ t♦t❛• r❡✇❛r❞ ♠♦❞❡• ✇✐t❤ t❤♦s❡ ✐♥ t❤❡ r❡s♣❡❝t✐✈❡ ❛✈❡r❛❣❡ r❡✇❛r❞ ♠♦❞❡•✳ ❚❤✐s r❡•❛t✐♦♥ ✐♥ ✉s❡❞ ❛ ❝♦✉♣•❡ ♦❢ t✐♠❡s ✐♥ ♦✉r ♣r♦♦❢s✳ ◆♦✇ ✇❡ ❝❛♥ ❢♦r♠✉•❛t❡ ♦✉r ♠❛✐♥ r❡s✉•t ♦❢ t❤✐s s❡❝t✐♦♥✳ ❚❤❡♦r❡♠ ✷ ❊✈❡r② ❛♥♦♥②♠♦✉s s❡q✉❡♥t✐❛• ❣❛♠❡ ✇✐t❤ t♦t❛• r❡✇❛r❞ s❛t✐s❢②✐♥❣ ✭❚✶✮ ❤❛s ❛ st❛t✐♦♥❛r② ❡q✉✐•✐❜r✐✉♠✳ ❆s ✐♥ t❤❡ ❝❛s❡ ♦❢ t❤❡ ❛✈❡r❛❣❡ r❡✇❛r❞✱ ✇❡ st❛rt ❜② ❞❡✜♥✐♥❣ s♦♠❡ ❛❞❞✐t✐♦♥❛• ♥♦t❛t✐♦♥✳ ▲❡t M(τ ) ❜❡ ❛ ♠♦❞✐✜❡❞ ▼❛r❦♦✈ ❞❡❝✐s✐♦♥ ♣r♦❝❡ss ♦❢ ❛♥ ✐♥❞✐✈✐❞✉❛• ❢❛❝❡❞ ✇✐t❤ ❛ ✜①❡❞ ✭♦✈❡r t✐♠❡✮ ❞✐str✐❜✉t✐♦♥ ♦❢ st❛t❡✲❛❝t✐♦♥ ♣❛✐rs ♦❢ ❛•• t❤❡ ♦t❤❡r ♣•❛②❡rs✳ ❚❤✐s ♠♦❞✐✜❝❛t✐♦♥ ✐s s•✐❣❤t ❜✉t ✐♠♣♦rt❛♥t✱ ♥❛♠❡•② ✇❡ ❛ss✉♠❡ t❤❛t ✐♥ M(τ ) t❤❡ st❛t❡ s 0 ✐s ❛❜s♦r❜✐♥❣ ❛♥❞ t❤❡ r❡✇❛r❞ ✐♥ t❤✐s st❛t❡ ✐s ❛•✇❛②s ✵✳ ❚❤✐s ✐s ❛ ❝•❛ss✐❝ ▼❉P ✇✐t❤ t♦t❛• r❡✇❛r❞✱ ❛s ❝♦♥s✐❞❡r❡❞ ✐♥ t❤❡ •✐t❡r❛t✉r❡✳ ❋♦r t❤✐s ✜①❡❞ τ ∈ ∆(S × A) •❡t J τ (f, ρ) ❞❡♥♦t❡ t❤❡ t♦t❛• ♣❛②♦✛ ✐♥ t❤✐s ♣r♦❝❡ss ✇❤❡♥ t❤❡ ♣•❛②❡r ✉s❡s st❛t✐♦♥❛r② ♣♦•✐❝② f ❛♥❞ t❤❡ ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ ♦❢ st❛t❡s ✐s ρ✱ ❛♥❞ •❡t G(τ ) ❞❡♥♦t❡ t❤❡ ♦♣t✐♠❛• r❡✇❛r❞ ✐♥ M(τ )✱ t❤❛t ✐s G(τ ) = sup f :S→A J τ (f, Q(•|s 0 , a 0 , τ )). ❲❡ ❝❛♥ ♣r♦✈❡ t❤❡ ❢♦••♦✇✐♥❣ ❛✉①✐•✐❛r② r❡s✉•t✿ ▲❡♠♠❛ ✸ ❯♥❞❡r ✭❚✶✮ J τ (f, ρ) ✐s ❛ ✭•♦✐♥t•②✮ ❝♦♥t✐♥✉♦✉s ❢✉♥❝t✐♦♥ ♦❢ ρ✱ f ❛♥❞ τ ✳ Pr♦♦❢✿ ❇② ❛ ✇❡•• ❦♥♦✇♥ r❡s✉•t ❢r♦♠ t❤❡ t❤❡♦r② ♦❢ ▼❛r❦♦✈ ❞❡❝✐s✐♦♥ ♣r♦❝❡ss❡s ✭s❡❡ ❡✳❣✳ ❬✸✷(✱ ▲❡♠♠❛ ✼✳✶✳✽ ✕ ❛ss✉♠♣t✐♦♥ ♦❢ t❤✐s •❡♠♠❛ ✐s s❛t✐s✜❡❞ ❛s ❛ ❝♦♥s❡q✉❡♥❝❡ ♦❢ ❛ss✉♠♣t✐♦♥ ✭❚✶✮ ❛♥❞ t❤❡ ❢❛❝t t❤❛t ❢✉♥❝t✐♦♥ u ✐s ❝♦♥t✐♥✉♦✉s ♦♥ ❛ ❝♦♠♣❛❝t s❡t ❛♥❞ t❤✉s ❜♦✉♥❞❡❞✮✱ J τ (f, ρ) ✐s t❤❡ •✐♠✐t ♦❢ t❤❡ r❡✇❛r❞s ✐♥ r❡s♣❡❝t✐✈❡ ❞✐s❝♦✉♥t❡❞ ▼❉Ps J τ β (f, ρ) ❛s t❤❡ ❞✐s❝♦✉♥t ❢❛❝t♦r β ❛♣♣r♦❛❝❤❡s ✶✳ ❙✐♥❝❡ ❜② ❛ ✇❡•• ❦♥♦✇♥ r❡s✉•t ✭s❡❡ ❡✳❣✳ ▲❡♠♠❛ ✽✳✺ ✐♥ ❬✸✼(✮ ❞✐s❝♦✉♥t❡❞ r❡✇❛r❞s ❛r❡ ❝♦♥t✐♥✉♦✉s ❢✉♥❝t✐♦♥s ♦❢ st❛t✐♦♥❛r② ♣♦•✐❝✐❡s ❛♥❞ t❤❡② ❛r❡ •✐♥❡❛r ✐♥ t❤❡ ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ ♦❢ st❛t❡s✱ t♦ s❤♦✇ t❤❡ ❝♦♥t✐♥✉✐t② ♦❢ J τ (f, ρ) ✐t ✐s ❡♥♦✉❣❤ t♦ ♣r♦✈❡ t❤❛t t❤❡ ❝♦♥✈❡r❣❡♥❝❡ ♦❢ J τ β (f, ρ) ✐s ✉♥✐❢♦r♠✳ ▲❡t ✉s t❛❦❡ ❛♥ ε > 0 ❛♥❞ s❡t M = max s,a,τ |u(s, a, τ )| ✭s✉❝❤ ❛ ♥✉♠❜❡r ❡①✐sts ❛s u ✐s ❛ ❝♦♥t✐♥✉♦✉s ❢✉♥❝t✐♦♥ ❞❡✜♥❡❞ ♦♥ ❛ ❝♦♠♣❛❝t s❡t✮✳ ❚❤❡ ♣r♦❜❛❜✐•✐t② t❤❛t ❛❢t❡r m(|S| -1) st❡♣s t❤❡ st❛t❡ ♦❢ ❛♥ ✐♥❞✐✈✐❞✉❛• ❞✐❞ ♥♦t r❡❛❝❤ s 0 ✐s ❢♦r ❛♥② st❛t✐♦♥❛r② ♣♦•✐❝② f ❜② ❛ss✉♠♣t✐♦♥ ✭❚✶✮ ♥♦t ❣r❡❛t❡r t❤❛♥ (1 -p 0 ) m ✳ ❚❤✐s ♠❡❛♥s t❤❛t ❢♦r ❛♥② m✱ J τ (f, ρ) - m(|S|-1) t=1 E ρ,Q,f u(s t , a t , τ ) ≤ M (|S| -1)(1 -p 0 ) m , ✭✺✮ ✇❤✐❝❤ ❢♦r m ❜✐❣ ❡♥♦✉❣❤✱ s❛② ❜✐❣❣❡r t❤❛♥ m ε ✱ ✐s ♥♦t ❣r❡❛t❡r t❤❛♥ ε 3 ✳ ◆♦t❡ t❤❛t ❛♥❛•♦❣♦✉s•② ❢♦r m ≥ m ε ❛♥❞ ❛♥② β ∈ (0, 1) J τ β (f, ρ) - m(|S|-1) t=1 E ρ,Q,f β t-1 u(s t , a t , τ ) < ε 3 , ✭✻✮ ◆❡①t ♥♦t❡ t❤❛t m(|S|-1) t=1 E ρ,Q,f u(s t , a t , τ ) - m(|S|-1) t=1 E ρ,Q,f β t-1 u(s t , a t , τ ) ≤ M (1-β m(|S|-1) ) ≤ ε 3 ✭✼✮ ❢♦r β ❜✐❣ ❡♥♦✉❣❤✱ s❛② β > β ε ✳ ❈♦♠❜✐♥✐♥❣ ✭✺✮✱ ✭✻✮ ❛♥❞ ✭✼✮ ❛♥❞ ✉s✐♥❣ t❤❡ tr✐❛♥❣•❡ ✐♥❡q✉❛•✐t② ✇❡ ♦❜t❛✐♥✿ J τ (f, ρ) -J τ β (f, ρ) ≤ J τ (f, ρ) - m(|S|-1) t=1 E ρ,Q,f u(s t , a t , τ ) ✶✷ + m(|S|-1) t=1 E ρ,Q,f u(s t , a t , τ ) - m(|S|-1) t=1 E ρ,Q,f β t-1 u(s t , a t , τ ) + m(|S|-1) t=1 E ρ,Q,f β t-1 u(s t , a t , τ ) -J τ β (f, ρ) ≤ ε 3 + ε 3 + ε 3 = ε ❢♦r β > β ε ✱ ✇❤✐❝❤ ❡♥❞s t❤❡ ♣r♦♦❢✳ Pr♦♦❢ ♦❢ ❚❤❡♦r❡♠ ✷✿ ❲❡ s❤❛•• ❝♦♥s✐❞❡r t✇♦ ♠✉•t✐❢✉♥❝t✐♦♥s ♦❢ τ ∈ ∆(S × A)✿ B(τ ) : =    ρ ∈ ∆(S × A) : ∃f ρ ∈ U ∀s ∈ S, a∈A ρ sa > 0 ⇒ f ρ (s) = ρ sa a∈A ρ sa ❛♥❞ J τ (f ρ , Q(•|s 0 , a 0 , τ )) = G(τ )    C(τ ) = ρ ∈ ∆(S × A) : a∈A ρ sa = x∈S b∈B Q(s|x, b, τ )ρ xb ❛♥❞ •❡t Ψ (τ ) := B(τ ) ∩ C(τ )✳ ❲❡ ✇✐•• s❤♦✇ t❤❛t Ψ ❤❛s ❛ ✜①❡❞ ♣♦✐♥t ❛♥❞ t❤❛t ✐t ❝♦rr❡s♣♦♥❞s t♦ ❛♥ ❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ ❣❛♠❡✳ ❋✐rst ♥♦t❡ t❤❛t Ψ (τ ) ✐s ♥♦♥❡♠♣t② ❢♦r ❛♥② τ ∈ ∆(S × A)✱ ❛s ❛♥② ✐♥✈❛r✐✲ ❛♥t ♠❡❛s✉r❡ ❝♦rr❡s♣♦♥❞✐♥❣ t♦ ❛♥ ♦♣t✐♠❛• st❛t✐♦♥❛r② ♣♦•✐❝② ✐♥ M(τ ) ❜❡•♦♥❣s t♦ Ψ (τ ) ✭s✉❝❤ ❛♥ ♦♣t✐♠❛• st❛t✐♦♥❛r② ♣♦•✐❝② ❡①✐sts ❛❝❝♦r❞✐♥❣ t♦ ❚❤❡♦r❡♠ ✼✳✶✳✾ ✐♥ ❬✸✷(✮✳ ◆❡①t ✇❡ s❤♦✇ t❤❛t Ψ (τ ) ✐s ❝♦♥✈❡① ❢♦r ❡✈❡r② τ ∈ ∆(S × A)✳ ❇② t❤❡ r❡♥❡✇❛• t❤❡♦r❡♠ ✭❚❤❡♦r❡♠ ✸✳✸✳✹ ✐♥ ❬✸✽(✮ t❤❡ t♦t❛• r❡✇❛r❞ ♦❝❝✉♣❛t✐♦♥ ♠❡❛s✉r❡ ❝♦rr❡s♣♦♥❞✐♥❣ t♦ s♦♠❡ st❛t✐♦♥❛r② ♣♦•✐❝② f ✐s ❡q✉❛• t♦ t❤❡ ❛✈❡r❛❣❡ r❡✇❛r❞ ♦❝✲ ❝✉♣❛t✐♦♥ ♠❡❛s✉r❡ ✉♥❞❡r t❤❡ s❛♠❡ ♣♦•✐❝② ♠✉•t✐♣•✐❡❞ ❜② t❤❡ ❡①♣❡❝t❡❞ •✐❢❡t✐♠❡✳ ❚❤✐s ✐♠♣•✐❡s t❤❛t ❢♦r ❛♥② ρ ∈ Ψ (τ ) ✭t❤❡ ♥♦t❛t✐♦♥ ✉s❡❞ ❤❡r❡ ✐s t❤❡ s❛♠❡ ❛s ✐♥ t❤❡ ❞❡✜♥✐t✐♦♥ ♦❢ B(τ )✮✿ G(τ ) = J τ (f ρ , Q(•|s 0 , a 0 , τ )) = E Q,f T s∈S a∈A ρ sa u(s, a, τ ). ✭✽✮ ◆❡①t ♥♦t❡ t❤❛t t❤❡ t✐♠❡ s♣❡♥t ✐♥ st❛t❡ s 0 ✱ ♣•❛②✐♥❣ ❛❝t✐♦♥ a 0 ✐s ✐♥❞❡♣❡♥❞❡♥t ♦❢ t❤❡ ♣♦•✐❝② ✉s❡❞ ❜② t❤❡ ♣•❛②❡r✳ ❲❡ s❤❛•• ❞❡♥♦t❡ t❤✐s t✐♠❡ ❜② T 0 ✳ ❆❣❛✐♥ ❜② t❤❡ r❡♥❡✇❛• t❤❡♦r❡♠ ✇❡ ❝❛♥ ✇r✐t❡ E Q T 0 = E Q,f T ρ s0a0 s∈S a∈A ρ sa = E Q,f T ρ s0a0 . ❙✉❜st✐t✉t✐♥❣ t❤✐s ✐♥t♦ ✭✽✮ ✇❡ ♦❜t❛✐♥ G(τ ) = E Q T 0 ρ s0a0 s∈S a∈A ρ sa u(s, a, τ ) ♦r ❡q✉✐✈❛•❡♥t•② E Q T 0 s∈S a∈A ρ sa u(s, a, τ ) -G(τ )ρ s0a0 = 0. ❚❤❡ s❡t ♦❢ ♣r♦❜❛❜✐•✐t② ♠❡❛s✉r❡s ρ s❛t✐s❢②✐♥❣ t❤❡ ❛❜♦✈❡ ❡q✉❛•✐t② ✐s ❝•❡❛r•② ❛ ♣♦•②t♦♣❡✱ ❛♥❞ ❤❡♥❝❡ ❛ ❝♦♥✈❡① s❡t✳ ❲❤❛t ✇❡ ❛r❡ •❡❢t t♦ s❤♦✇ ✐s t❤❛t t❤❡ ❣r❛♣❤ ♦❢ Ψ ✐s ❝•♦s❡❞✳ ❙✉♣♣♦s❡ t❤❛t τ n , τ, ρ n , ρ ∈ ∆(S × A)✱ τ n → τ ✱ ρ n → ρ ❛♥❞ ρ n ∈ Ψ (τ n ) ❢♦r ❡✈❡r② n✳ ❇② ▲❡♠♠❛ ✶ ρ ∈ C(τ )✳ ❈•❡❛r•②✱ ❛s ρ n → ρ✱ ❛•s♦ f ρn → f ρ ✳ ❙✐♥❝❡ ρ n ∈ B(τ n )✱ G(τ n ) = J τn (f ρn , Q(•|s o , a 0 , τ n )) ≥ J τn (g, Q(•|s o , a 0 , τ n )) ❢♦r ❛♥② st❛t✐♦♥❛r② str❛t❡❣② g✳ ❇② ▲❡♠♠❛ ✸ ❛♥❞ t❤❡ ❝♦♥t✐♥✉✐t② ♦❢ Q ❛•s♦ J τ (f ρ , Q(•|s o , a 0 , τ )) ≥ J τ (g, Q(•|s o , a 0 , τ )), ✐♠♣•②✐♥❣ t❤❛t ρ ∈ B(τ ) ❛♥❞ ❤❡♥❝❡ ❛•s♦ ✐♥ Ψ (τ )✳ ❚❤✐s ♠❡❛♥s t❤❛t ❛•• t❤❡ ❛ss✉♠♣t✐♦♥s ♦❢ t❤❡ ••✐❝❦s❜❡r❣ t❤❡♦r❡♠ ❬✸✻( ❛r❡ s❛t✐s✜❡❞ ❛♥❞ Ψ ❤❛s ❛ ✜①❡❞ ♣♦✐♥t✳ ◆♦✇ s✉♣♣♦s❡ τ * ✐s t❤✐s ✜①❡❞ ♣♦✐♥t✳ ❇❡❝❛✉s❡ τ * ∈ C(τ * )✱ ✐t s❛t✐s✜❡s a∈A τ * sa = x∈S b∈B Q(s|x, b, τ * )τ * xb = Φ(s|τ * ). ❖♥ t❤❡ ♦t❤❡r ❤❛♥❞✱ ♥♦t✐❝❡ t❤❛t J(τ * S , g, f τ * ) = J τ * (g, ρ) ❢♦r ❛♥② st❛t✐♦♥❛r② ♣♦•✐❝② g ❛♥❞ ❛♥② ✐♥✐t✐❛• st❛t❡ ❞✐str✐❜✉t✐♦♥ ρ✱ ❛♥❞ s♦ τ * ∈ B(τ * ) ✐♠♣•✐❡s t❤❛t f τ * ✐s t❤❡ ❜❡st r❡s♣♦♥s❡ ♦❢ ❛ ♣•❛②❡r ✇❤❡♥ t❤❡ st❛t❡✲❛❝t✐♦♥ ❞✐str✐❜✉t✐♦♥ ♦❢ ❤✐s ♦♣♦♥❡♥ts ✐s ❛•✇❛②s τ * ✱ ❛♥❞ ❤❡♥❝❡ (f * , τ * S ) ✇✐t❤ f * (s, τ ) ≡ f τ * (s) ❢♦r ❛♥② τ ∈ ∆(S × A) ✐s ❛♥ ❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ ❣❛♠❡✳ ✺ ❚❤❡ |❡•❛t✐♦♥ ✇✐t❤ •❛♠❡s ✇✐t❤ ❋✐♥✐t❡•② ▼❛♥② P•❛②❡rs ▼❛✐♥ ♣♦✐♥t ♦❢ ❝r✐t✐❝✐s♠ ♦❢ ❛♥♦♥②♠♦✉s ❣❛♠❡s ✐♥ ❣❡♥❡r❛• ✐s t❤❛t t❤❡ •✐♠✐t✐♥❣ s✐t✉❛t✐♦♥ ✇✐t❤ ❛♥ ✐♥✜♥✐t❡ ♥✉♠❜❡r ♦❢ ♣•❛②❡rs ❞♦❡s ♥♦t ❡①✐st ✐♥ r❡❛•✐t②✱ ❛♥❞ t❤✉s ✐t ✐s ♥♦t s✉r❡ t❤❛t t❤❡ r❡s✉•ts ♦❜t❛✐♥❡❞ ❢♦r ❛ ❝♦♥t✐♥✉✉♠ ♦❢ ♣•❛②❡rs ❛r❡ r❡•❡✈❛♥t ❢♦r t❤❡ r❡❛•✲•✐❢❡ ♦♥❡s✱ ✇❤❡♥ t❤❡ ♥✉♠❜❡r ♦❢ ♣•❛②❡rs ✐s ✜♥✐t❡✱ ❜✉t •❛r❣❡✳ ■♥ t❤✐s s❡❝t✐♦♥ ✇❡ ♣r❡s❡♥t s♦♠❡ r❡s✉•ts ❝♦♥♥❡❝t✐♥❣ t❤❡ ❛♥♦♥②♠♦✉s ❣❛♠❡ ♠♦❞❡•s ❢r♦♠ ♣r❡✈✐♦✉s s❡❝t✐♦♥s ✇✐t❤ s✐♠✐•❛r ♠♦❞❡•s ✇✐t❤ ✜♥✐t❡•② ♠❛♥② ♣•❛②❡rs✳ ■♥ t❤❡s❡ r❡s✉•ts ✇❡ ✇✐••✱ ✐♥ ❛❞❞✐t✐♦♥✱ ✉s❡ t❤❡ ❢♦••♦✇✐♥❣ t✇♦ ❛ss✉♠♣t✐♦♥s✳ ✭❆❚✶✮ Q(•|a, s, τ ) = Q(•|a, s) ❢♦r ❛•• τ ∈ ∆(S × A) ❛♥❞ A(•, µ) = A(•) ❢♦r ❛•• µ ∈ ∆(S)✳ ✭❆❚✷✮ ❋♦r ❛♥② f ∈ U ❛♥❞ τ ∈ ∆(S ×A) t❤❡ ▼❛r❦♦✈ ❝❤❛✐♥ ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ♦❢ ❛♥ ✐♥❞✐✈✐❞✉❛• ✉s✐♥❣ f ✇❤❡♥ t❤❡ st❛t❡✲❛❝t✐♦♥ ❞✐str✐❜✉t✐♦♥ ♦❢ ❛•• t❤❡ ♦t❤❡r ♣•❛②❡rs ✐s τ ✐s ❛♣❡r✐♦❞✐❝✳ ❚❤❡ ❛ss✉♠♣t✐♦♥s s✐♠✐•✐❛r t♦ ✭❆❚✶✮ ❛♣♣❡❛r ❛•s♦ ✐♥ ❛ r❡❝❡♥t ♣❛♣❡r ❬✸✾( ♦♥ st♦❝❤❛st✐❝ ❣❛♠❡s ✇✐t❤ ❛ ✜♥✐t❡ ♥✉♠❜❡r ♦❢ ♣•❛②❡rs ❛♥❞ ❛✈❡r❛❣❡ r❡✇❛r❞✳ ❚❤❡② ❛r❡ ❛•s♦ ✉s❡❞ ✐♥ s♦♠❡ ♣❛♣❡rs ♦♥ ▼❛r❦♦✈ ❡✈♦•✉t✐♦♥❛r② ❣❛♠❡s ❬✷✾✱ ✸✵( ❛♥❞ ✐♥ ❛ r❡❝❡♥t ❛♣♣•✐❝❛t✐♦♥ ♦❢ ❛♥♦♥②♠♦✉s s❡q✉❡♥t✐❛• ❣❛♠❡s t♦ ♠♦❞❡• ♣♦✇❡r ❝♦♥tr♦• ♣r♦❜•❡♠ ✐♥ ❛ ✇✐r❡•❡ss ♥❡t✇♦r❦ ❬✷✼(✳ ■t ❛••♦✇s t♦ ❞❡❝♦✉♣•❡ t❤❡ ▼❛r❦♦✈ ❝❤❛✐♥s ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ❢♦r ❡❛❝❤ ♦❢ t❤❡ ♣•❛②❡rs ✭s♦ t❤❛t t❤❡ ❞❡♣❡♥❞❡♥❝❡ ❜❡t✇❡❡♥ ❞✐✛❡r❡♥t ♣•❛②❡rs ✐s ♦♥•② t❤r♦✉❣❤ r❡✇❛r❞s✮ ✕ t❤✐s ❞❡❝♦✉♣•✐♥❣ ✐s ❝r✉❝✐❛• ✐♥ ♦✉r ♣r♦♦❢s ♦❢ ❝♦♥✈❡r❣❡♥❝❡ ♦❢ ❣❛♠❡s ✇✐t❤ ✜♥✐t❡ ♥✉♠❜❡r ♦❢ ♣•❛②❡rs t♦ r❡s♣❡❝t✐✈❡ ❛♥♦♥②♠♦✉s ♠♦❞❡•s✳ ■♠♣♦rt❛♥t•② t❤♦✉❣❤✱ ✐♥ ♠♦st ❡♥❣✐♥❡❡r✐♥❣ ❛♣♣•✐❝❛t✐♦♥s ✐♥✲ ❞✐✈✐❞✉❛• st❛t❡ ♦❢ ❛ ♣•❛②❡r ✐s ❡✐t❤❡r ❤✐s ❡♥❡r❣② ✭♦r s♦♠❡ ♦t❤❡r ♣r✐✈❛t❡ r❡s♦✉r❝❡✮ •❡✈❡• ♦r ❤✐s ❣❡♦❣r❛♣❤✐❝❛• ♣♦s✐t✐♦♥✳ ■♥ ❜♦t❤ ❝❛s❡s ❛ss✉♠♣t✐♦♥ ✭❆❚✶✮ ✐s ♥❛t✉r❛••② s❛t✐s✜❡❞✳ ❲❡ ✇✐•• ♥❡❡❞ t♦ ❞❡✜♥❡ s♦♠❡ ❛❞❞✐t✐♦♥❛• ♥♦t❛t✐♦♥✳ ✕ ❲❡ s❛② t❤❛t ❛♥ n✲♣❡rs♦♥ st♦❝❤❛st✐❝ ❣❛♠❡ ✐s t❤❡ n✲♣❡rs♦♥ ❝♦✉♥t❡r♣❛rt ♦❢ ❛♥ ❛♥♦♥②♠♦✉s ❣❛♠❡ ✐❢ ✐t ✐s ❞❡✜♥❡❞ ✇✐t❤ t❤❡ s❛♠❡ ♦❜•❡❝ts S✱ A✱ u ❛♥❞ Q✱ ✇✐t❤ t❤❡ ❞✐✛❡r❡♥❝❡ t❤❛t t❤❡ ♥✉♠❜❡r ♦❢ ♣•❛②❡rs ✐s n ❛♥❞ ✐♥ ❝♦♥s❡q✉❡♥❝❡ t❤❡ ❣•♦❜❛• st❛t❡s ❛♥❞ st❛t❡✲❛❝t✐♦♥ ❞✐str✐❜✉t✐♦♥s ❛r❡ ❞❡✜♥❡❞ ♦♥ s✉❜s❡ts ♦❢ ∆(S) ❛♥❞ ∆(S × A)✱ ∆ n (S) := {µ ∈ ∆(S) : µ s = k s n , k s ∈ N, ❢♦r ❛•• s ∈ S}, ∆ n (S × A) := {τ ∈ ∆(S × A) : a∈A τ sa = k s n , k s ∈ N, ❢♦r ❛•• s ∈ S}. ✕ ❲❡ ✇✐•• ❝♦♥s✐❞❡r ❛ ✇✐❞❡r s❡t ♦❢ ♣♦ss✐❜•❡ ♣♦•✐❝✐❡s ✐♥ t❤❡ ❣❛♠❡✳ ◆❛♠❡•②✱ ✇❡ ✇✐•• ❝♦♥s✐❞❡r ❛ s✐t✉❛t✐♦♥ ✇❤❡♥ ❡❛❝❤ ♣•❛②❡r ✉s❡s ❛ st❛t✐♦♥❛r② ♣♦•✐❝② ♦✈❡r t❤❡ ✇❤♦•❡ ❣❛♠❡✱ ❜✉t t❤✐s ♣♦•✐❝② ✐s ❝❤♦s❡♥ ❛t t❤❡ ❜❡❣✐♥♥✐♥❣ ♦❢ t❤❡ ♣•❛② ❛❝❝♦r❞✐♥❣ t♦ s♦♠❡ ♣r♦❜❛❜✐•✐t② ❞✐str✐❜✉t✐♦♥✳ ❚❤✐s ♠❡❛♥s t❤❛t ❛♥② ♣r♦❜❛❜✐•✐t② ❞✐str✐❜✉t✐♦♥ ❢r♦♠ ∆(U ) ✇✐•• ❜❡ ❛ ♣♦•✐❝② ✐♥ t❤❡ ❣❛♠❡✳ ✕ ❲❡ ✇✐•• ❝♦♥s✐❞❡r ❛ ❞✐✛❡r❡♥t ✭✐✳❡✳ st❛♥❞❛r❞✮ ❞❡✜♥✐t✐♦♥ ♦❢ ♣♦•✐❝✐❡s ❛♥❞ ❡q✉✐✲ •✐❜r✐✉♠ ✐♥ t❤❡ ❛✈❡r❛❣❡✲r❡✇❛r❞ ❣❛♠❡✳ ❲❡ ✇✐•• s❛② t❤❛t ♣♦•✐❝✐❡s (f 1 , . . . , f n ) ❢♦r♠ ❛ ◆❛s❤ ❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ ❛✈❡r❛❣❡✲r❡✇❛r❞ n✲♣❡rs♦♥ ❣❛♠❡ ✐❢ ❢♦r ❛♥② ♣•❛②❡r i ❛♥❞ ❛♥② ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ ♦❢ t❤❡ ❣•♦❜❛• st❛t❡ µ 1 ✱ J i (µ 1 , f 1 , . . . , f i , . . . , f n ) ≥ J i (µ 1 , f 1 , . . . , g i , . . . , f n ) ❢♦r ❛♥② ♦t❤❡r ♣♦•✐❝② g i ✳ ■❢ t❤✐s ✐♥❡q✉❛•✐t② ❤♦•❞s ✉♣ t♦ s♦♠❡ ε✱ ✇❡ s❛② t❤❛t (f 1 , . . . , f n ) ❛r❡ ✐♥ ε✲❡q✉✐•✐❜r✐✉♠✳ ❋♦r ❜♦t❤ ♠♦❞❡•s ✭✇✐t❤ ❛✈❡r❛❣❡ ❛♥❞ t♦t❛• r❡✇❛r❞✮ ✇❡ ✇✐•• ❛•s♦ ❝♦♥s✐❞❡r t❤❡ ♥♦t✐♦♥ ♦❢ ❡q✉✐•✐❜r✐✉♠ ❞❡✜♥❡❞ ❛s ❢♦r t❤❡ ❛♥♦♥②♠♦✉s ❣❛♠❡ ✕ ✇❡ ✇✐•• ❝❛•• ✐t t❤❡♥ ❛ ✇❡❛❦ ❡q✉✐•✐❜r✐✉♠ ✭❛♥❞ ❛♥❛•♦❣♦✉s•② ❞❡✜♥❡ ✇❡❛❦ ε✲❡q✉✐•✐❜r✐✉♠✮✳ ◆♦✇ ✇❡ ❝❛♥ ♣r♦✈❡ t❤❡ ❢♦••♦✇✐♥❣ t✇♦ r❡s✉•ts✿ ❚❤❡♦r❡♠ ✸ ❙✉♣♣♦s❡ (f, µ) ✐s ❛♥ ❡q✉✐•✐❜r✐✉♠ ✐♥ ❡✐t❤❡r ❛♥ ❛✈❡r❛❣❡ r❡✇❛r❞ ❛♥♦♥②♠♦✉s ❣❛♠❡ s❛t✐s❢②✐♥❣ ✭❆✶✮ ❛♥❞ ✭❆❚✶✮ ♦r ❛ t♦t❛• r❡✇❛r❞ ❛♥♦♥②♠♦✉s ❣❛♠❡ s❛t✐s❢②✐♥❣ ✭❚✶✮ ❛♥❞ ✭❆❚✶✮✳ ❚❤❡♥ ❢♦r ❡✈❡r② ε > 0 t❤❡r❡ ❡①✐sts ❛♥ n ε s✉❝❤ t❤❛t ❢♦r ❡✈❡r② n ≥ n ε (f, µ) ✐s ❛ ✇❡❛❦ ❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ n✲♣❡rs♦♥ ❝♦✉♥t❡r♣❛rt ♦❢ t❤✐s ❛♥♦♥②♠♦✉s ❣❛♠❡✳ ✶✺ ❆ str♦♥❣❡r r❡s✉•t ✐s tr✉❡ ❢♦r t❤❡ ❛✈❡r❛❣❡ r❡✇❛r❞ ❣❛♠❡✿ ❚❤❡♦r❡♠ ✹ ❋♦r ❡✈❡r② ε > 0 t❤❡r❡ ❡①✐sts ❛♥ n ε s✉❝❤ t❤❛t ❢♦r ❡✈❡r② n ≥ n ε t❤❡ n✲♣❡rs♦♥ ❝♦✉♥t❡r♣❛rt ♦❢ t❤❡ ❛✈❡r❛❣❡✲r❡✇❛r❞ ❛♥♦♥②♠♦✉s ❣❛♠❡ s❛t✐s❢②✐♥❣ ✭❆✶✮✱ ✭❆❚✶✮ ❛♥❞ ✭❆❚✷✮ ❤❛s ❛ s②♠♠❡tr✐❝ ◆❛s❤ ❡q✉✐•✐❜r✐✉♠ (π n , . . . , π n )✱ ✇❤❡r❡ π n ∈ ∆(U )✳ ▼♦r❡♦✈❡r ✐❢ (f, µ) ✐s ❛♥ ❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ ❛♥♦♥②♠♦✉s ❣❛♠❡✱ t❤❡♥ π n ✐s ♦❢ t❤❡ ❢♦r♠✿ π n (s) = l µ * l δ[f n l (s)], ✇❤❡r❡ f n l (s) = f (s) ✐❢ s ∈ S l f (s) ✐❢ s ∈ S l , f ✐s t❤❡ ❝♦♠♠✉♥✐❝❛t✐♥❣ ♣♦•✐❝② ✐♥❞✉❝❡❞ ❜② t❤❡ ❛ss✉♠♣t✐♦♥ ✭❆✶✮ ✽ ✱ S l ❛r❡ ❡r❣♦❞✐❝ ❝•❛ss❡s ♦❢ t❤❡ ✐♥❞✐✈✐❞✉❛• st❛t❡ ♣r♦❝❡ss ♦❢ ❛ ♣•❛②❡r ✇❤❡♥ ❤❡ ❛♣♣•✐❡s ♣♦•✐❝② f ❛♥❞ µ * ✐s t❤❡ ♣r♦❜❛❜✐•✐t② ♠❡❛s✉r❡ ♦♥ t❤❡s❡ ❡r❣♦❞✐❝ ❝•❛ss❡s ❝♦rr❡s♣♦♥❞✐♥❣ t♦ ♠❡❛s✉r❡ µ ♦✈❡r S ✾ ✳ Pr♦♦❢ ♦❢ ❚❤❡♦r❡♠ ✸✿ ▲❡t J (µ, g, f ) ❞❡♥♦t❡ t❤❡ r❡✇❛r❞ ✐♥ t❤❡ n✲♣❡rs♦♥ ❝♦✉♥t❡r♣❛rt ♦❢ t❤❡ ❣✐✈❡♥ ❛✈❡r❛❣❡✲r❡✇❛r❞ ❛♥♦♥②♠♦✉s ❣❛♠❡ ❢♦r ❛ ♣•❛②❡r ✉s✐♥❣ st❛t✐♦♥❛r② str❛t❡❣② g ❛❣❛✐♥st f ♦❢ ❛•• t❤❡ ♦t❤❡rs ✇❤❡♥ ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ✐s µ✳ J n (µ, g, f ) = lim T →∞ 1 T E g,f,µ,Q T t=1 u(s t , g(x t ), τ t ) = E f,µ,Q x,a σ xa (g)m n f (τ )u(x, a, τ ), ✇❤❡r❡ σ(g) ✐s t❤❡ ♦❝❝✉♣❛t✐♦♥ ♠❡❛s✉r❡ ♦❢ t❤❡ ♣r♦❝❡ss ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ♦❢ t❤❡ ♣•❛②❡r ✉s✐♥❣ ♣♦•✐❝② g ❛♥❞ m n f ✐s ❛ ♣r♦❜❛❜✐•✐t② ♠❡❛s✉r❡ ♦✈❡r t❤❡ s❡t ∆(S × A) ❞❡♥♦t✐♥❣ t❤❡ ❢r❡q✉❡♥❝② ♦❢ t❤❡ ❛♣♣❡❛r❛♥❝❡ ♦❢ ❞✐✛❡r❡♥t st❛t❡✲❛❝t✐♦♥ ♠❡❛s✉r❡s ♦❢ ❛•• t❤❡ ♣•❛②❡rs ♦✈❡r t❤❡ ❝♦✉rs❡ ♦❢ t❤❡ ❣❛♠❡✳ ◆♦t❡ ❢✉rt❤❡r t❤❛t σ(g) ✐s ✉♥❞❡r ✭❆❚✶✮ ✐♥❞❡♣❡♥❞❡♥t ♦❢ n ❛♥❞ t❤❡ s❛♠❡ ❛s ✐♥ t❤❡ •✐♠✐t✐♥❣ ✭❛♥♦♥②♠♦✉s ❣❛♠❡✮ ❝❛s❡✳ ❖♥ t❤❡ ♦t❤❡r ❤❛♥❞ m n f ❝♦♥✈❡r❣❡s ✇❡❛❦•② ❛s n ❣♦❡s t♦ ✐♥✜♥✐t② t♦ t❤❡ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ❝♦rr❡s♣♦♥❞✐♥❣ t♦ t❤❡ ♣♦•✐❝② f ❛♥❞ t❤❡ ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ µ✳ ❚❤✉s J n (µ, g, f ) → n→∞ J(µ, g, f ) ❢♦r ❛♥② st❛t✐♦♥❛r② str❛t❡❣② g✳ ❚❤❡ t❤❡s✐s ♦❢ t❤❡ t❤❡♦r❡♠ ❢♦••♦✇s ✐♠♠❡❞✐❛t❡•②✳ ❚♦ ♣r♦✈❡ t❤❡ t♦t❛• r❡✇❛r❞ ❝❛s❡ ✇❡ ✜rst ♥❡❡❞ t♦ ✇r✐t❡ t❤❡ r❡✇❛r❞ ✐♥ t❤❡ n✲♣❡rs♦♥ ❝♦✉♥t❡r♣❛rt ♦❢ t❤❡ ❣✐✈❡♥ t♦t❛• r❡✇❛r❞ ❛♥♦♥②♠♦✉s ❣❛♠❡ ❢♦r ❛ ♣•❛②❡r ✉s✐♥❣ st❛t✐♦♥❛r② str❛t❡❣② g ❛❣❛✐♥st f ♦❢ ❛•• t❤❡ ♦t❤❡rs ✇❤❡♥ ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ ♦❢ st❛t❡s ✐s µ✳ J n (µ, g, f ) = E g,f,µ,Q T t=1 u(s t , g(x t ), τ t ). ✽ ❍❡r❡ ✐t ❞♦❡s ♥♦t ❞❡♣❡♥❞ ♦♥ τ ❜② ✭❆❚✶✮✳ ✾ ◆♦t❡ t❤❛t ❛ ♠❡❛s✉r❡ ♦✈❡r t❤❡ s❡t ♦❢ st❛t❡s ♦❢ ❛♥ ❛♣❡r✐♦❞✐❝ ▼❛r❦♦✈ ♣r♦❝❡ss ❝❛♥ ❜❡ ✐♥✈❛r✐❛♥t ♦♥•② ✐❢ ✐t ✐s ❛ ❝♦♥✈❡① ❝♦♠❜✐♥❛t✐♦♥ ♦❢ ✉♥✐q✉❡ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡s ♦♥ ❡❛❝❤ ♦❢ t❤❡ ❡r❣♦❞✐❝ ❝•❛ss❡s✳ ❚❤❡ ❝♦❡✣❝✐❡♥ts ♦❢ t❤✐s ❝♦♥✈❡① ❝♦♠❜✐♥❛t✐♦♥ ❛r❡ ❡①❛❝t•② t❤❡ µ * l ✳ ✇✐t❤ s 1 ❞✐str✐❜✉t❡❞ ❛❝❝♦r❞✐♥❣ t♦ Q(•|s 0 , a 0 ) ✭r❡❝❛•• t❤❛t ❜② ✭❆❚✶✮ t❤✐s ❞✐str✐✲ ❜✉t✐♦♥ ✐s ✐♥❞❡♣❡♥❞❡♥t ♦❢ t❤❡ ❣•♦❜❛• st❛t❡✲❛❝t✐♦♥ ❞✐str✐❜✉t✐♦♥ τ ✮✳ ❚❤✐s ❜② t❤❡ r❡♥❡✇❛• t❤❡♦r❡♠ ❡q✉❛•s E g,µ,Q T (g) x,a σ xa (g)m n f (τ )u(x, a, τ ), ✇❤❡r❡ σ(g) ✐s t❤❡ ♦❝❝✉♣❛t✐♦♥ ♠❡❛s✉r❡ ♦❢ t❤❡ ♣r♦❝❡ss ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ♦❢ t❤❡ ♣•❛②❡r ✉s✐♥❣ ♣♦•✐❝② g ❛♥❞ m n f ✐s ❛ ♣r♦❜❛❜✐•✐t② ♠❡❛s✉r❡ ♦✈❡r t❤❡ s❡t ∆(S × A) ❞❡♥♦t✐♥❣ t❤❡ ❢r❡q✉❡♥❝② ♦❢ t❤❡ ❛♣♣❡❛r❛♥❝❡ ♦❢ ❞✐✛❡r❡♥t st❛t❡✲❛❝t✐♦♥ ♠❡❛s✉r❡s ♦❢ ❛•• t❤❡ ♣•❛②❡rs ♦✈❡r t❤❡ ❝♦✉rs❡ ♦❢ t❤❡ ❣❛♠❡✳ ❇✉t ❜♦t❤ σ(g) ❛♥❞ E g,µ,Q T (g) ❛r❡ ✉♥❞❡r ✭❆❚✶✮ ✐♥❞❡♣❡♥❞❡♥t ♦❢ n ❛♥❞ t❤❡ s❛♠❡ ❛s ✐♥ t❤❡ •✐♠✐t✐♥❣ ✭❛♥♦♥②♠♦✉s ❣❛♠❡✮ ❝❛s❡✱ ✇❤✐•❡ m n f ❝♦♥✈❡r❣❡s ✇❡❛❦•② t♦ t❤❡ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ❝♦rr❡s♣♦♥❞✐♥❣ t♦ t❤❡ ♣♦•✐❝② f ❛♥❞ t❤❡ ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ µ ❛s n → ∞✳ ❚❤❡ t❤❡s✐s ♦❢ t❤❡ t❤❡♦r❡♠ ✐s ♥♦✇ ♦❜t❛✐♥❡❞ ❛s ✐♥ t❤❡ ❛✈❡r❛❣❡ r❡✇❛r❞ ❝❛s❡✳ Pr♦♦❢ ♦❢ ❚❤❡♦r❡♠ ✹✿ ❋✐① ε > 0 ❛♥❞ t❛❦❡ n ε s✉❝❤ t❤❛t ❢♦r ❡✈❡r② n ≥ n ε (f, . . . , f ) ✐s ❛ ✇❡❛❦ ε✲❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ n✲♣❡rs♦♥ ❝♦✉♥t❡r♣❛rt ♦❢ t❤❡ ❛✈❡r❛❣❡✲ r❡✇❛r❞ ❣❛♠❡✳ ◆❡①t ♥♦t❡ t❤❛t ❢♦r ❡✈❡r② n ∈ N t❤❡ ♣r♦❝❡ss ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ♦❢ ❡❛❝❤ ♦❢ t❤❡ ♣•❛②❡rs ✉s✐♥❣ ♣♦•✐❝② π n ❤❛s ❛ ✉♥✐q✉❡ ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ µ✳ ❙✐♥❝❡ ❜② ✭❆❚✷✮ t❤❡ ♣r♦❝❡ss ♦❢ ✐♥❞✐✈✐❞✉❛• st❛t❡s ✐s ❛♣❡r✐♦❞✐❝✱ ✐t ✇✐•• ❝♦♥✈❡r❣❡ t♦ t❤✐s ✐♥✈❛r✐❛♥t ♠❡❛s✉r❡ ❛♥❞✱ ❝♦♥s❡q✉❡♥t•②✱ t❤❡ r❡✇❛r❞ ❢♦r ❛ ♣•❛②❡r ✉s✐♥❣ ♣♦•✐❝② f ❛❣❛✐♥st f ♦❢ ❛•• t❤❡ ♦t❤❡rs ✇✐•• ❜❡ ❡q✉❛• t♦ J(µ, f, f ) ❢♦r ❛♥② ✐♥✐t✐❛• st❛t❡ ❞✐str✐✲ ❜✉t✐♦♥✳ ❍♦✇❡✈❡r✱ s✐♥❝❡ ✐♥ ❛ ✇❡❛❦•② ❝♦♠♠✉♥✐❝❛t✐♥❣ ▼❛r❦♦✈ ❞❡❝✐s✐♦♥ ♣r♦❝❡ss t❤❡ ♦♣t✐♠❛• ❣❛✐♥ ✐s ✐♥❞❡♣❡♥❞❡♥t ♦❢ t❤✐s ❞✐str✐❜✉t✐♦♥ ❛♥❞ s✐♥❝❡ (f, . . . , f ) ✐s ❛ ✇❡❛❦ ε✲❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ n✲♣❡rs♦♥ ❣❛♠❡ ❢♦r n ≥ n ε ✱ ✐t ✐s ❛•s♦ ❛ ◆❛s❤ ε✲❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ n✲♣❡rs♦♥ ❣❛♠❡✳ ✻ ❆♣♣•✐❝❛t✐♦♥✿ ▼❡❞✐✉♠ ❆❝❝❡ss •❛♠❡ ■♥ t❤❡ r❡♠❛✐♥❞❡r ♦❢ t❤❡ ♣❛♣❡r ✇❡ ♣r❡s❡♥t t✇♦ s✐♠♣•❡ ❡①❛♠♣•❡s ♦❢ ❛♣♣•✐❝❛t✐♦♥ ♦❢ ♦✉r ❢r❛♠❡✇♦r❦ t♦ ♠♦❞❡• s♦♠❡ r❡❛•✲•✐❢❡ ♣❤❡♥♦♠❡♥❛✳ ✻✳✶ ❚❤❡ ▼♦❞❡• ❈♦♥s✐❞❡r t❤❡ ❢♦••♦✇✐♥❣ ▼❆❈ ✭▼❡❞✐✉♠ ❆❈❝❡ss✮ ❣❛♠❡ ❜❡t✇❡❡♥ ♠♦❜✐•❡ ♣❤♦♥❡s✳ ❚✐♠❡ ✐s s•♦tt❡❞✳ ❆t ❛♥② ❣✐✈❡♥ t✐♠❡ t✱ ❛ ♠♦❜✐•❡ ✜♥❞s ✐ts❡•❢ ❝♦♠♣❡t✐♥❣ ✇✐t❤ N t ♦t❤❡r ♠♦❜✐•❡s ❢♦r t❤❡ ❛❝❝❡ss t♦ ❛ ❝❤❛♥♥❡•✳ N t ✐s ❛ss✉♠❡❞ t♦ ❤❛✈❡ P♦✐ss♦♥ ❞✐str✐✲ ❜✉t✐♦♥ ✇✐t❤ ♣❛r❛♠❡t❡r λ✳ ❲❡ s❤❛•• ❢♦r♠✉•❛t❡ t❤✐s ❛s ❛ s❡q✉❡♥t✐❛• ❛♥♦♥②♠♦✉s ❣❛♠❡ ❛s ❢♦••♦✇s✳ ✕ ■♥❞✐✈✐❞✉❛• st❛t❡ ❆ ♠♦❜✐•❡ ❤❛s t❤r❡❡ ♣♦ss✐❜•❡ st❛t❡s✿ F ✭❢✉••✮ AE ✭❆•♠♦st ❊♠♣t②✮ ❛♥❞ E ✭❊♠♣t②✮✳ ✕ ❆❝t✐♦♥s ❚❤❡r❡ ❛r❡ t✇♦ ❛❝t✐♦♥s✿ tr❛♥s♠✐t ❛t ❤✐❣❤ ♣♦✇❡r H ♦r •♦✇ ♣♦✇❡r L✳ ❆t st❛t❡ AE ❛ ♠♦❜✐•❡ ❝❛♥♥♦t tr❛♥s♠✐t ❛t ❤✐❣❤ ♣♦✇❡r✱ ✇❤✐•❡ ❛t E ✐t ❝❛♥♥♦t tr❛♥s♠✐t ❛t ❛••✳ ✕ ❚r❛♥s✐t✐♦♥ ♣r♦❜❛❜✐•✐t✐❡s ❋r♦♠ st❛t❡ AE t❤❡ ♠♦❜✐•❡ ♠♦✈❡s t♦ st❛t❡ E ✇✐t❤ ♣r♦❜❛❜✐•✐t② p E ❛♥❞ ♦t❤❡r✇✐s❡ r❡♠❛✐♥s ✐♥ AE✳ ❆t st❛t❡ E t❤❡ ♠♦❜✐•❡ ❤❛s t♦ r❡❝❤❛r❣❡✳ ■t ♠♦✈❡s t♦ st❛t❡ F ❛❢t❡r ♦♥❡ t✐♠❡ ✉♥✐t✳ ❆ ♠♦❜✐•❡ ✐♥ st❛t❡ F tr❛♥s♠✐tt✐♥❣ ✇✐t❤ ♣♦✇❡r r ♠♦✈❡s t♦ st❛t❡ AE ✇✐t❤ ♣r♦❜❛❜✐•✐t② ♣r♦♣♦rt✐♦♥❛• t♦ r ❛♥❞ ❣✐✈❡♥ ❜② αr ❢♦r s♦♠❡ ❝♦♥st❛♥t α > 0✳ ✕ P❛②♦✛ ❈♦♥s✐❞❡r ❛ ❣✐✈❡♥ ❝❡••✉•❛r ♣❤♦♥❡ t❤❛t tr❛♥s♠✐ts ❛ ♣❛❝❦❡t✳ ❆ss✉♠❡ t❤❛t x ♦t❤❡r ♣❛❝❦❡ts ❛r❡ tr❛♥s♠✐tt❡❞ ✇✐t❤ ❤✐❣❤ ♣♦✇❡r ❛♥❞ y ✇✐t❤ •♦✇ ♣♦✇❡r t♦ t❤❡ s❛♠❡ ❜❛s❡ st❛t✐♦♥✳ ❆ ♣❛❝❦❡t tr❛♥s♠✐tt❡❞ ✇✐t❤ •♦✇ ♣♦✇❡r ✐s r❡❝❡✐✈❡❞ s✉❝❝❡ss❢✉••② ✇✐t❤ s♦♠❡ ♣r♦❜❛❜✐•✐t② q ✐❢ ✐t ✐s t❤❡ ♦♥•② ♣❛❝❦❡t tr❛♥s♠✐tt❡❞✱ ✐✳❡✳ y = 0✱ x = 0✳ ❖t❤❡r✇✐s❡ ✐t ✐s •♦st✳ ❆ ♣❛❝❦❡t tr❛♥s♠✐tt❡❞ ✇✐t❤ ❤✐❣❤ ♣♦✇❡r ✐s r❡❝❡✐✈❡❞ s✉❝❝❡ss❢✉••② ✇✐t❤ s♦♠❡ ♣r♦❜❛❜✐•✐t② Q > q ✐❢ ✐t ✐s t❤❡ ♦♥•② ♣❛❝❦❡t tr❛♥s♠✐tt❡❞ ❛t ❤✐❣❤ ♣♦✇❡r✱ ✐✳❡✳ x = 0✳ ❚❤❡ ✐♠♠❡❞✐❛t❡ ♣❛②♦✛ ✐s 1 ✐❢ t❤❡ ♣❛❝❦❡t ✐s s✉❝❝❡ss❢✉••② tr❛♥s♠✐tt❡❞✳ ■t ✐s ♦t❤❡r✇✐s❡ ③❡r♦✳ ■♥ ❛❞❞✐t✐♦♥ t❤❡r❡ ✐s ❛ ❝♦♥st❛♥t ❝♦st c > 0 ❢♦r r❡❝❤❛r❣✐♥❣ t❤❡ ❜❛tt❡r②✳ ❆❣❣r❡❣❛t❡ ✉t✐•✐t② ❢♦r ❛ ♣•❛②❡r ✐s t❤❡♥ ❝♦♠♣✉t❡❞ ❛s •♦♥❣✲t✐♠❡ ❛✈❡r❛❣❡ ♦❢ t❤❡ ♣❡r✲♣❡r✐♦❞ ♣❛②♦✛s✳ ❙✉♣♣♦s❡ p ✐s t❤❡ ❢r❛❝t✐♦♥ ♦❢ ♣♦♣✉•❛t✐♦♥ t❤❛t tr❛♥s♠✐ts ❛t ❤✐❣❤ ♣♦✇❡r ✐♥ st❛t❡ F ✱ ❛♥❞ t❤❛t µ F ✱ µ AE ❛♥❞ µ E ❛r❡ ❢r❛❝t✐♦♥s ♦❢ ♣•❛②❡rs ✐♥ r❡s♣❡❝t✐✈❡ st❛t❡s✳ ❚❤❡♥ ♣r♦❜❛❜✐•✐t② ♦❢ s✉❝❝❡ss ❢♦r ❛ ♣•❛②❡r tr❛♥s♠✐tt✐♥❣ ❛t ❤✐❣❤ ♣♦✇❡r ✐s QP (x = 0) = Q(e -λ + ∞ k=1 λ k k! e -λ (1 -pµ F ) k = Qe -λ e λ(1-pµ F ) = Qe -λpµ F , ✇❤✐•❡ ♣r♦❜❛❜✐•✐t② ♦❢ s✉❝❝❡ss ✇❤❡♥ ❛ ♣•❛②❡r tr❛♥s♠✐ts ❛t •♦✇ ♣♦✇❡r ✐s qP (x + y = 0) = q(e -λ + ∞ k=1 λ k k! e -λ µ k E ) = qe -λ e λµ E = qe λ(µ E -1) . ❚❤❡s❡ ✈❛•✉❡s ❞♦ ♥♦t ❞❡♣❡♥❞ ♦♥ ❛❝t✉❛• ♥✉♠❜❡rs ♦❢ ♣•❛②❡rs ❛♣♣•②✐♥❣ r❡s♣❡❝t✐✈❡ str❛t❡❣✐❡s ✕ ♦♥•② ♦♥ ❢r❛❝t✐♦♥s ♦❢ ♣•❛②❡rs ✐♥ ❡❛❝❤ ♦❢ t❤❡ st❛t❡s ✉s✐♥❣ ❞✐✛❡r❡♥t ❛❝✲ t✐♦♥s✳ ❚❤✉s ✐♥st❡❛❞ ♦❢ ❝♦♥s✐❞❡r✐♥❣ ❛♥ n✲♣•❛②❡r ❣❛♠❡ ❢♦r ❛♥② ✜①❡❞ n ✐t ✐s r❡❛s♦♥✲ ❛❜•❡ t♦ ❛♣♣•② t❤❡ ❛♥♦♥②♠♦✉s ❣❛♠❡ ❢♦r♠✉•❛t✐♦♥ ✇✐t❤ τ = [τ F,H , τ F,L , τ AE,L , τ E ] ❞❡♥♦t✐♥❣ t❤❡ ✈❡❝t♦r ♦❢ ❢r❛❝t✐♦♥s ♦❢ ♣•❛②❡rs ✐♥ r❡s♣❡❝t✐✈❡ st❛t❡s ❛♥❞ ✉s✐♥❣ r❡✲ s♣❡❝t✐✈❡ ❛❝t✐♦♥s✱ ✇✐t❤ ✐♠♠❡❞✐❛t❡ r❡✇❛r❞s u(s, a, τ ) =    Qe -λτ F,H , ✇❤❡♥ a = H qe λ(τ E -1) , ✇❤❡♥ a = L -c, ✇❤❡♥ s = E ❛♥❞ tr❛♥s✐t✐♦♥ ♣r♦❜❛❜✐•✐t✐❡s ❞❡✜♥❡❞ ❜② ♠❛tr✐① Q(a, τ ) =   1 -αa αa 0 0 1 -p E p E 1 0 0   . ✻✳✷ ❚❤❡ ❙♦•✉t✐♦♥ ❚❤❡ st❛t✐♦♥❛r② st❛t❡ ♦❢ t❤❡ ❝❤❛✐♥ ♦❢ t❤❡ ♣r✐✈❛t❡ st❛t❡s ♦❢ ❛ ♣•❛②❡r ✉s✐♥❣ ♣♦•✐❝② f ♣r❡s❝r✐❜✐♥❣ ❤✐♠ t♦ ✉s❡ ❤✐❣❤ ♣♦✇❡r ✇✐t❤ ♣r♦❜❛❜✐•✐t② p ✇❤❡♥ ✐♥ st❛t❡ F ✐s 1 α(pH + (1 -p)L)(p E + 1) + p E [p E , α(pH + (1 -p)L), p E α(pH + (1 -p)L)] . ❚❤✉s ❝♦♠♣✉t❛t✐♦♥s ②✐❡•❞ t❤❛t ❤✐s r❡s♣❡❝t❡❞ •♦♥❣✲r✉♥ ❛✈❡r❛❣❡ r❡✇❛r❞ ✐s ♦❢ t❤❡ ❢♦r♠ Ap + B Cp + D ✇✐t❤ A = p E Qe -λτ F,H + ((H -L)α -p E )qe λ(τ E -1) -cαp E (H -L), B = (Lα + p E )qe λ(τ E -1) -cαp E L, C = α(H -L)(p E + 1), D = αL(p e + 1) + p E . ■t ❝❛♥ ❜❡ ❡✐t❤❡r ❛ str✐❝t•② ✐♥❝r❡❛s✐♥❣✱ ❛ ❝♦♥st❛♥t ♦r ❛ str✐❝t•② ❞❡❝r❡❛s✐♥❣ ❢✉♥❝t✐♦♥ ♦❢ p✱ ❞❡♣❡♥❞✐♥❣ ♦♥ ✇❤❡t❤❡r AD > BC✱ AD = BC ♦r AD < BC✱ ❛♥❞ t❤✉s t❤❡ ❜❡st r❡s♣♦♥s❡ ♦❢ ❛ ♣•❛②❡r ❛❣❛✐♥st t❤❡ ❛❣❣r❡❣❛t❡❞ st❛t❡✲❛❝t✐♦♥ ✈❡❝t♦r τ ✐s p = 1 ✇❤❡♥ AD > BC✱ ❛♥② p ∈ [0, 1] ✇❤❡♥ AD = BC ♦r p = 0 ✇❤❡♥ AD < BC✳ ❚❤✐s •❡❛❞s t♦ t❤❡ ❢♦••♦✇✐♥❣ ❝♦♥❝•✉s✐♦♥✿ s✐♥❝❡ ❜② ❚❤❡♦r❡♠ ✶ t❤✐s ❛♥♦♥②♠♦✉s ❣❛♠❡ ❤❛s ❛♥ ❡q✉✐•✐❜r✐✉♠✱ ♦♥❡ ♦❢ t❤❡ t❤r❡❡ ❢♦••♦✇✐♥❣ ❝❛s❡s ♠✉st ❤♦•❞✿ ✭❛✮ ■❢ p E Qe - λp E αH(p E +1)+p E + ((H -L)α -p E )qe - λ(αH+p E ) αH(p E +1)+p E -aαp E (H -L) [αL(p E + 1) + p E ] > (Lα + p E )qe - λ(αH+p E ) αH(p E +1)+p E -cαLp E [α(H -L)(p E + 1)] t❤❡♥ ❛•• t❤❡ ♣•❛②❡rs ✉s❡ ❤✐❣❤ ♣♦✇❡r ✐♥ st❛t❡ F ❛t ❡q✉✐•✐❜r✐✉♠✳ ✭❜✮ ■❢ p E Qe - λp E αL(p E +1)+p E + ((H -L)α -p E )qe - λ(αL+p E ) αL(p E +1)+p E -aαp E (H -L) [αL(p E + 1) + p E ] < (Lα + p E )qe - λ(αL+p E ) αL(p E +1)+p E -cαLp E [α(H -L)(p E + 1)] t❤❡♥ ❛•• t❤❡ ♣•❛②❡rs ✉s❡ •♦✇ ♣♦✇❡r ✐♥ st❛t❡ F ❛t ❡q✉✐•✐❜r✐✉♠✳ ✭❝✮ ■❢ ♥♦♥❡ ♦❢ t❤❡ ❛❜♦✈❡ ✐♥❡q✉❛•✐t✐❡s ❤♦•❞s t❤❛♥ ✇❡ ♥❡❡❞ t♦ ✜♥❞ p * s❛t✐s❢②✐♥❣ p E Qe -λτ F,H + ((H -L)α -p E )qe λ(τ E -1) -cαp E (H -L) [αL(p e + 1) + p E ] = (Lα + p E )qe λ(τ E -1) -cαp E L [α(H -L)(p E + 1)] ✇✐t❤ τ F,H = p * p E α(p * H+(1-p * )L)(p E +1)+p E ❛♥❞ τ E = α(p * H+(1-p * )L)p E α(p * H+(1-p * )L)(p E +1)+p E ✳ ❚❤❡♥ ❛•• t❤❡ ♣•❛②❡rs ✉s❡ ♣♦•✐❝② ♣r❡s❝r✐❜✐♥❣ t♦ ✉s❡ ❤✐❣❤ ♣♦✇❡r ✇✐t❤ ♣r♦❜❛✲ ❜✐•✐t② p * ✐♥ st❛t❡ F ❛t ❡q✉✐•✐❜r✐✉♠✳ |❡♠❛r❦ ✸ ■t ✐s ✇♦rt❤ ♥♦t✐♥❣ ❤❡r❡ t❤❛t s♦♠❡ ❣❡♥❡r❛•✐③❛t✐♦♥s ♦❢ t❤❡ ♠♦❞❡• ♣r❡✲ s❡♥t❡❞ ❛❜♦✈❡ ❝❛♥ ❜❡ ❝♦♥s✐❞❡r❡❞✳ ❲❡ ❝❛♥ ❛ss✉♠❡ t❤❛t t❤❡r❡ ❛r❡ ♠♦r❡ ❡♥❡r❣② •❡✈❡•s ❛♥❞ ♠♦r❡ ♣♦✇❡rs ❛t ✇❤✐❝❤ ♣•❛②❡rs ❝♦✉•❞ tr❛♥s♠✐t ✐♥ ♦✉r ❣❛♠❡ ✭s✐♠✐•✲ ✐❛r•② ❛s ✐♥ ❬✷✼(✮✳ ❲❡ ❝❛♥ ❛•s♦ ❛ss✉♠❡ t❤❛t t❤❡ ♣•❛②❡rs ❞♦ ♥♦t ❛•✇❛②s tr❛♥s♠✐t✱ ♦♥•② ✇✐t❤ s♦♠❡ ♣♦s✐t✐✈❡ ♣r♦❜❛❜✐•✐t② ✭t❤❡♥ t❤❡ ✐♥❞✐✈✐❞✉❛• st❛t❡ ❜❡❝♦♠❡s t✇♦✲ ❞✐♠❡♥s✐♦♥❛•✱ ❝♦♥s✐st✐♥❣ ♦❢ ♣•❛②❡r✬s ❡♥❡r❣② st❛t❡ ❛♥❞ ❛♥ ✐♥❞✐❝❛t♦r ♦❢ ✇❤❡t❤❡r ❤❡ ❤❛s s♦♠❡t❤✐♥❣ t♦ tr❛♥s♠✐t ♦r ♥♦t✮✳ ❇♦t❤ t❤❡s❡ ❣❡♥❡r❛•✐③❛t✐♦♥s ❛r❡ tr❛❝t❛❜•❡ ✇✐t❤✐♥ ♦✉r ❢r❛♠❡✇♦r❦✱ t❤♦✉❣❤ t❤❡ ❝♦♠♣✉t❛t✐♦♥s ❜❡❝♦♠❡ ♠♦r❡ ✐♥✈♦•✈❡❞✳ ✼ ❚❤❡ ❈❛s❡ ♦❢ ▲✐♥❡❛r ❯t✐•✐t②✿ ▼❛✐♥t❡♥❛♥❝❡✲|❡♣❛✐r ❊①❛♠♣•❡ ✼✳✶ •❡♥❡r❛• ▲✐♥❡❛r ❋r❛♠❡✇♦r❦ ■♥ t❤❡ ♥❡①t ❡①❛♠♣•❡ ✇❡ ❝♦♥s✐❞❡r ❛ ❣❛♠❡ s❛t✐s❢②✐♥❣ s♦♠❡ ❛❞❞✐t✐♦♥❛• ❛ss✉♠♣✲ t✐♦♥s✳ ▲❡t K = (S × A)✳ ▲❡t u(τ ) ❜❡ ❛ ❝♦•✉♠♥ ✈❡❝t♦r ✇❤♦s❡ ❡♥tr✐❡s ❛r❡ u(k, τ )✳ ❲❡ ❝♦♥s✐❞❡r ♥♦✇ t❤❡ s♣❡❝✐❛• ❝❛s❡ t❤❛t u(k, τ ) ✐s •✐♥❡❛r ✐♥ τ ✳ ❊q✉✐✈❛•❡♥t•②✱ t❤❡r❡ ❛r❡ s♦♠❡ ✈❡❝t♦r u 1 ♦✈❡r K ❛♥❞ ❛ ♠❛tr✐① u 2 ♦❢ ❞✐♠❡♥s✐♦♥ |K| × |K| s✉❝❤ t❤❛t u(τ ) = u 1 + u 2 τ ❙✐♠✐•❛r•②✱ ✇❡ ❛ss✉♠❡ t❤❛t t❤❡ tr❛♥s✐t✐♦♥ ♣r♦❜❛❜✐•✐t✐❡s ❛r❡ •✐♥❡❛r ✐♥ τ ✳ ❚❤❡♥ t❤❡ ❣❛♠❡ ❜❡❝♦♠❡s ❡q✉✐✈❛•❡♥t t♦ s♦•✈✐♥❣ ❛ s②♠♠❡tr✐❝ ❜✐•✐♥❡❛r ❣❛♠❡✱ t❤❛t ♦❢ ✜♥❞✐♥❣ ❛ ✜①❡❞ ♣♦✐♥t ♦❢ ✭✷✮✲✭✸✮✳ ▲✐♥❡❛r ❝♦♠♣•❡♠❡♥t❛r✐t② ❢♦r♠✉•❛t✐♦♥ ❝❛♥ ❜❡ ✉s❡❞ ❛♥❞ s♦•✈❡❞ ✉s✐♥❣ ▲❡♠❦❡✬s ❛•❣♦r✐t❤♠✳ ❋r♦♠ t❤❡ s♦•✉t✐♦♥ τ ✱ t❤❡ ❡q✉✐•✐❜r✐✉♠ (f, τ S ) ❝❛♥ ❜❡ ❞❡r✐✈❡❞ ✇✐t❤ ❛ ❤❡•♣ ♦❢ ❡q✉❛t✐♦♥ ✭✹✮✳ ✼✳✷ ▼❛✐♥t❡♥❛♥❝❡✲|❡♣❛✐r •❛♠❡✿ ❚❤❡ ▼♦❞❡• ❚❤❡ ♠❛✐♥t❡♥❡♥❝❡✲r❡♣❛✐r ❡①❛♠♣•❡ ♣r❡s❡♥t❡❞ ❜❡•♦✇ ❝❛♥ ❜❡ s❡❡♥ ❛s ❛ t♦② ♠♦❞❡•✳ ■ts ♠❛✐♥ ♣✉r♣♦s❡ t❤♦✉❣❤ ✐s t♦ s❤♦✇ ❤♦✇ t❤❡ ❛❜♦✈❡♠❡♥t✐♦♥❡❞ ♠❡t❤♦❞ ❝❛♥ ❜❡ ✉s❡❞ ✐♥ ❛ ❝♦♥❝r❡t❡ ❣❛♠❡ s❛t✐s❢②✐♥❣ t❤❡ •✐♥❡❛r✐t② ❝♦♥❞✐t✐♦♥s ♠❡♥t✐♦♥❡❞ ❛❜♦✈❡✳ ❊❛❝❤ ❝❛r ❛♠♦♥❣ ❛ •❛r❣❡ ♥✉♠❜❡r ♦❢ ❝❛rs ✐s s✉♣♣♦s❡❞ t♦ ❞r✐✈❡ ♦♥❡ ✉♥✐t ♦❢ ❞✐st❛♥❝❡ ♣❡r ❞❛②✳ ❆ ❝❛r ✐s ✐♥ ♦♥❡ ♦❢ t❤❡ ✐♥❞✐✈✐❞✉❛• st❛t❡s ❣♦♦❞ ✭g✮ ❛♥❞ ❜❛❞ ✭b✮✳ ❲❤❡♥ ❛ ❝❛r ✐s ✐♥ ❛ ❜❛❞ st❛t❡ t❤❡♥ ✐t ❤❛s t♦ ❣♦ t❤r♦✉❣❤ s♦♠❡ ♠❛✐♥t❡♥❛♥❝❡ ❛♥❞ r❡♣❛✐r ❛❝t✐♦♥s ❛♥❞ ❝❛♥♥♦t ❞r✐✈❡ ❢♦r s♦♠❡ ✭❣❡♦♠❡tr✐❝❛••② ❞✐str✐❜✉t❡❞✮ t✐♠❡✳ ❆ s✐♥❣•❡ ❞r✐✈❡r ✐s ❛ss✉♠❡❞ t♦ ❜❡ ✐♥✜♥✐t❡s✐♠❛•② ✏s♠❛••✑ ✐♥ t❤❡ s❡♥s❡ t❤❛t ✐ts ❝♦♥tr✐❜✉t✐♦♥ t♦ t❤❡ ❝♦♥❣❡st✐♦♥ ❡①♣❡r✐❡♥❝❡❞ ❜② ♦t❤❡r ❝❛rs ✐s ♥❡❣•✐❣✐❜•❡✳ ❲❡ ❛ss✉♠❡ t❤❛t t❤❡r❡ ❛r❡ t✇♦ t②♣❡s ♦❢ ❜❡❤❛✈✐♦r ♦❢ ❞r✐✈❡rs✳ ❚❤♦s❡ t❤❛t ❞r✐✈❡ ❣❡♥t•②✱ ❛♥❞ t❤♦s❡ t❤❛t t❛❦❡ r✐s❦s ❛♥❞ ❞r✐✈❡ ❢❛st✳ ❚❤✐s ❝❤♦✐❝❡ ✐s ♠♦❞❡•❡❞ ♠❛t❤✲ ❡♠❛t✐❝❛••② t❤r♦✉❣❤ t✇♦ ❛❝t✐♦♥s✿ ❛❣❣r❡ss✐✈❡ ✭α✮ ❛♥❞ ❣❡♥t•❡ ✭γ✮✳ ❆♥ ❛❣❣r❡ss✐✈❡
t♦ ❛ss✉♠❡ t❤❛t t❤❡ ❝♦♥tr✐❜✉t✐♦♥ t♦ t❤❡ t♦t❛• ❝♦♥❣❡st✐♦♥ ✐s β t✐♠❡s •♦✇❡r t❤❛♥ t❤❛t ♦❢ t❤❡ ♦t❤❡r ❞r✐✈❡rs✳ ▼♦r❡ ❢♦r♠❛••②✱ •❡t η ❜❡ ❛ ❞❡•❛② ❢✉♥❝t✐♦♥✳ ❚❤❡♥ t❤❡ ❞❛✐•② ❝♦♥❣❡st✐♦♥ ❝♦st D ♦❢ ❛ ❞r✐✈❡r ✐s ❣✐✈❡♥ ❛s u(g, α, τ ) = u(g, γ, τ )/β u(g, γ, τ ) = -η (τ (g, γ) + τ (g, α)/β)) ❋♦r t❤❡ st❛t❡ b ✇❡ s❡t s✐♠♣•② u(b, a, τ ) = -1 ✇❤✐❝❤ r❡♣r❡s❡♥ts ❛ ♣❡♥❛•t② ❢♦r ❜❡✐♥❣ ✐♥ ❛ ♥♦♥✲♦♣❡r❛t✐♦♥❛• st❛t❡✳ ■t ❞♦❡s ♥♦t ❞❡♣❡♥❞ ♦♥ a ♥♦r τ ✳ ❚r❛♥s✐t✐♦♥ ♣r♦❜❛❜✐•✐t✐❡s✿ ❲❡ ❛ss✉♠❡ t❤❛t tr❛♥s✐t✐♦♥s ❢r♦♠ g t♦ b ♦❝✲ ❝✉r ❞✉❡ t♦ ❝♦••✐s✐♦♥s ❜❡t✇❡❡♥ ❝❛rs✳ ❋✉rt❤❡r ❛ss✉♠❡ t❤❛t t❤❡ ❝♦••✐s✐♦♥ ✐♥t❡♥s✐t② ❜❡t✇❡❡♥ ❛ ❝❛r t❤❛t ❞r✐✈❡s ❛t st❛t❡ g ❛♥❞ ✉s❡s ❛❝t✐♦♥ a ❛r❡ •✐♥❡❛r ✐♥ τ ✳ ▼♦r❡ ♣r❡❝✐s❡•②✱ Q(b|g, a, τ ) = c γ a τ (g, γ) + c α a τ (g, α). ❲❡ ♥❛t✉r❛••② ❛ss✉♠❡ t❤❛t c a α > c a γ ❢♦r a = α, γ ❛♥❞ t❤❛t c α a > c γ a ❢♦r a = γ, α✳ ■❢ ❛ ❞r✐✈❡r ✐s ♠♦r❡ ❛❣❣r❡ss✐✈❡ t❤❛♥ ❛♥♦t❤❡r ♦♥❡✱ ♦r ✐❢ t❤❡ r❡st ♦❢ t❤❡ ♣♦♣✉•❛t✐♦♥ ✐s ♠♦r❡ ❛❣❣r❡ss✐✈❡ t❤❡♥ t❤❡ ♣r♦❜❛❜✐•✐t② ♦❢ ❛ tr❛♥s✐t✐♦♥ ❢r♦♠ g t♦ b ✐♥❝r❡❛s❡s✳ ❲❡ r❡✇r✐t❡ t❤❡ ❛❜♦✈❡ ❛s Q(b|g, a, τ ) = c a • τ (g, .) ■❢ ❛ r❛♥❞♦♠✐③❡❞ st❛t✐♦♥❛r② ♣♦•✐❝② ✐s ✉s❡❞ ✇❤✐❝❤ ❝❤♦♦s❡s (α, γ) ✇✐t❤ r❡s♣❡❝t✐✈❡ ♣r♦❜❛❜✐•✐t✐❡s (p α , p γ ) =: p t❤❡♥ t❤❡ ♦♥❡ st❡♣ tr❛♥s✐t✐♦♥ ❢r♦♠ Q t♦ b ♦❝❝✉rs ✇✐t❤ ♣r♦❜❛❜✐•✐t② Q(b|g, p, τ ) = a=γ,α p a c a • τ (g, .) =: p • c • τ (g, .). ❖♥❝❡ ✐♥ st❛t❡ b✱ t❤❡ t✐♠❡ t♦ ❣❡t ✜①❡❞ ❞♦❡s ♥♦t ❞❡♣❡♥❞ ❛♥② ♠♦r❡ ♦♥ t❤❡ ❡♥✈✐r♦♥♠❡♥t✱ ❛♥❞ t❤❡ ❞r✐✈❡rs ❞♦ ♥♦t t❛❦❡ ❛♥② ❛❝t✐♦♥ ❛t t❤❛t st❛t❡✳ ❚❤✉s ψ := Q(g|b, a, τ ) ✐s s♦♠❡ ❝♦♥st❛♥t t❤❛t ✐s t❤❡ s❛♠❡ ❢♦r ❛•• a ❛♥❞ τ ✳ ✼✳✸ ❚❤❡ ❙♦•✉t✐♦♥ ❲❡ s❤❛•• ❛ss✉♠❡ t❤r♦✉❣❤♦✉t t❤❛t t❤❡ ❝♦♥❣❡st✐♦♥ ❢✉♥❝t✐♦♥ η ✐s •✐♥❡❛r✳ ■t t❤❡♥ ❢♦••♦✇s t❤❛t t❤✐s ♣r♦❜•❡♠ ❢❛••s ✐♥t♦ t❤❡ ❝❛t❡❣♦r② ♦❢ ❙❡❝t✐♦♥ ✼✳✶✳ ▲❡t τ ❜❡ ❣✐✈❡♥✳ ▲❡t ❛ ❞r✐✈❡r ✉s❡ ❛ st❛t✐♦♥❛r② ♣♦•✐❝② p✳ ❚❤❡♥ t❤❡ ❡①♣❡❝t❡❞ t✐♠❡ ✐t r❡♠❛✐♥s ✐♥ st❛t❡ g ✐s σ(p, τ ) = 1 Q(b|g, p, τ ) ✷✶ ■ts t♦t❛• ❡①♣❡❝t❡❞ ✉t✐•✐t② ❞✉r✐♥❣ t❤❛t t✐♠❡ ✐s W g (p, τ ) = σ(p, τ ) a p a u(g, a, τ ) = σ(p, τ ) a p a u(g, a, τ ) = -σ(p, τ ) p γ + p α β η (τ (g, γ) + τ (g, α)/β)) ❚❤❡ ❡①♣❡❝t❡❞ r❡♣❛✐r t✐♠❡ ♦❢ ❛ ❝❛r ✭t❤❡ ♣❡r✐♦❞ t❤❛t ❝♦♥s✐sts ♦❢ ❝♦♥s❡❝✉t✐✈❡ t✐♠❡ ✐t ✐s ✐♥ st❛t❡ b✮ ✐s ❣✐✈❡♥ ❜② ψ -1 ✳ ❚❤✉s t❤❡ t♦t❛• ❡①♣❡❝t❡❞ ✉t✐•✐t② ❞✉r✐♥❣ t❤❛t t✐♠❡ ✐s W b (p, τ ) = -ψ -1 . ❚❤✉s t❤❡ ❛✈❡r❛❣❡ ✉t✐•✐t② ✐s ❣✐✈❡♥ ❜② J(µ, p, π(τ )) = W g (p, τ )ψ -1 ψ Q(b|g,p,τ ) + 1 ✇❤❡r❡ µ ✐s ❛♥ ❛r❜✐tr❛r② ✐♥✐t✐❛• ❞✐str✐❜✉t✐♦♥ ❛♥❞ ✇❤❡r❡ π(τ ) ✐s t❤❡ st❛t✐♦♥❛r② ♣♦•✐❝② t❤❛t ✐s ♦❜t❛✐♥❡❞ ❢r♦♠ τ ❛s ✐♥ ✭✹✮✳ ▲❡t p * ❜❡ ❛ st❛t✐♦♥❛r② ❡q✉✐•✐❜r✐✉♠ ♣♦•✐❝② ❛♥❞ ❛ss✉♠❡ t❤❛t ✐t ✐s ♥♦t ♦♥ t❤❡ ❜♦✉♥❞❛r②✱ ✐✳❡✳ 0 < p * α < 1✳ ❲❡ s❤❛•• ❝♦♥s✐❞❡r t❤❡ ❡q✉✐✈❛•❡♥t ❜✐•✐♥❡❛r ❣❛♠❡✳ ▲❡t ρ * ❜❡ t❤❡ ♦❝❝✉♣❛t✐♦♥ ♠❡❛s✉r❡ ❝♦rr❡s♣♦♥❞✐♥❣ t♦ p * ✳ ■t ✐s ❛♥ ❡q✉✐•✐❜r✐✉♠ ✐♥ t❤❡ ❜✐•✐♥❡❛r ❣❛♠❡✳ ❙✐♥❝❡ t❤❡ ♦❜•❡❝t✐✈❡ ❢✉♥❝t✐♦♥ ✐s •✐♥❡❛r ✐♥ ρ✱ ρ * s❤♦✉•❞ ❜❡ s✉❝❤ t❤❛t ❡❛❝❤ ✐♥❞✐✈✐❞✉❛• ♣•❛②❡r ✐s ✐♥❞✐✛❡r❡♥t ❜❡t✇❡❡♥ ❛♥② st❛t✐♦♥❛r② ♣♦•✐❝②✳ ■♥ ♣❛rt✐❝✉•❛r✱ ✇❡ s❤♦✉•❞ ❤❛✈❡ J(µ, 1 α , π(τ )) = J(µ, 1 γ , π(τ )) ✇❤❡r❡ 1 a ✐s t❤❡ st❛t✐♦♥❛r② ♣✉r❡ ♣♦•✐❝② t❤❛t ❝❤♦♦s❡s ❛•✇❛②s a✳ ❲❡ t❤✉s ♦❜t❛✐♥ t❤❡ ❡q✉✐•✐❜r✐✉♠ ♦❝❝✉♣❛t✐♦♥ ♠❡❛s✉r❡ ρ * ❛s ❛ τ t❤❛t s❛t✐s✜❡s✿ W g (1 α , τ )ψ -1 ψ Q(b|g,α,τ ) + 1 = W g (1 γ , τ )ψ -1 ψ Q(b|g,γ,τ ) + 1 . ❚❤❡ ❡q✉✐•✐❜r✐✉♠ ♣♦•✐❝② p * ✐s ♦❜t❛✐♥❡❞ ❢r♦♠ ρ * ❛s ✐♥ ✭✹✮ ❛♥❞ t❤❡ ❡q✉✐•✐❜r✐✉♠ st❛t✐♦♥❛r② ♠❡❛s✉r❡ ✐s ρ * S ✳ ✽ ❉✐s❝✉ss✐♦♥ ❛♥❞ ❈♦♥❝•✉s✐♦♥s ❚❤❡ ❢r❛♠❡✇♦r❦ ♦❢ t❤❡ ❣❛♠❡ t❤❛t ✐s ❞❡✜♥❡❞ ✐♥ t❤✐s ♣❛♣❡r ✐s s✐♠✐•❛r ✐♥ ♥❛t✉r❡ t♦ t❤❡ ❝•❛ss✐❝❛• tr❛✣❝ ❛ss✐❣♥♠❡♥t ♣r♦❜•❡♠ ✐♥ t❤❛t ✐t ❤❛s ❛♥ ✐♥✜♥✐t② ♦❢ ♣•❛②❡rs✳ ■♥ ❜♦t❤ ❢r❛♠❡✇♦r❦s✱ ♣•❛②❡rs ❝❛♥ ❜❡ ✐♥ ❞✐✛❡r❡♥t st❛t❡s✳ ■♥ t❤❡ ❝•❛ss✐❝❛• tr❛❢✲ ✜❝ ❛ss✐❣♥♠❡♥t ♣r♦❜•❡♠✱ ❛ ❝•

  ❛②❡r ✉s✐♥❣ f τ ✐s ♣♦s✐t✐✈❡✳ ❆ss✉♠♣t✐♦♥ ✭❆✶✮ ❛♣♣❡❛rs ♦❢t❡♥ ✐♥ t❤❡ •✐t❡r❛t✉r❡ ♦♥ ▼❛r❦♦✈ ❞❡❝✐s✐♦♥ ♣r♦✲ ❝❡ss❡s ✇✐t❤ ❛✈❡r❛❣❡ ❝♦st ❛♥❞ ✐s r❡❢❡rr❡❞ t♦ ❛s ✏✇❡❛❦•② ❝♦♠♠✉♥✐❝❛t✐♥❣✑ ♣r♦♣❡rt②✱ s❡❡ ❡✳❣✳ ❬✸✷(✱ ❝❤❛♣t❡rs ✽ ❛♥❞ ✾✳ ✹ ■t ❣✉❛r❛♥t❡❡s t❤❛t t❤❡ ♦♣t✐♠❛• ❣❛✐♥ ✐♥ ❛ ▼❛r❦♦✈ ❞❡❝✐s✐♦♥ ♣r♦❝❡ss s❛t✐s❢②✐♥❣ ✐t ✐s ✐♥❞❡♣❡♥❞❡♥t ♦❢ ✐ts ✐♥✐t✐❛• st❛t❡✳ ❆s ✇❡ ✇✐•• s❡❡✱ ✐t ❛•s♦ ❣✉❛r❛♥t❡❡s t❤❛t t❤✐s ♦♣t✐♠❛• ❣❛✐♥ ✐s ❝♦♥t✐♥✉♦✉s ✐♥ τ ✱ ✇❤✐❝❤ ✇✐•• ❜❡ ❝r✉❝✐❛• ✐♥ ♣r♦✈✐♥❣ t❤❡ ❡①✐st❡♥❝❡ ♦❢ ❛♥ ❡q✉✐•✐❜r✐✉♠ ✐♥ ♦✉r ❣❛♠❡✳ ■t ✐s ❛•s♦ ✇♦rt❤ ♥♦t✲ ✐♥❣ t❤❛t ✇✐t❤♦✉t ❛ss✉♠♣t✐♦♥ ✭❆✶✮ t❤❡ ❛✈❡r❛❣❡✲r❡✇❛r❞ ❛♥♦♥②♠♦✉s s❡q✉❡♥t✐❛• ❣❛♠❡ ♠❛② ❤❛✈❡ ♥♦ st❛t✐♦♥❛r② ❡q✉✐•✐❜r✐❛ ❛t ❛••✳ ❚❤✐s ✐s s❤♦✇♥ ✐♥ t❤❡ ❢♦••♦✇✐♥❣ ❡①❛♠♣•❡ ✺ ❊①❛♠♣•❡ ✶ ▲❡t ✉s ❝♦♥s✐❞❡r ❛♥ ❛✈❡r❛❣❡ r❡✇❛r❞ ❛♥♦♥②♠♦✉s s❡q✉❡♥t✐❛• ❣❛♠❡ ✇✐t❤ S = {1, 2, 3} ❛♥❞ A(s, µ) = {0, 1}, ✐❢ s = 1 {0}, ♦t❤❡r✇✐s❡ ✱ t❤✉s t❤❡ ❞❡❝✐s✐♦♥ ✐s ♦♥•② ♠❛❞❡ ❜② ♣•❛②❡rs ✐♥ st❛t❡ 1✳ ❋♦r t❤❡ s✐♠♣•✐❝✐t② ✇❡ ✇✐•• ❞❡♥♦t❡ t❤✐s ♦♥•② ❞❡❝✐s✐♦♥ ❜② a ✐♥ ✇❤❛t ✇✐•• ❢♦••♦✇✳ ❚❤❡ ✐♠♠❡❞✐❛t❡ r❡✇❛r❞s ❢♦r t❤❡ ♣•❛②❡rs ❞❡♣❡♥❞ ♦♥•② ♦♥t❤❡✐r ♣r✐✈❛t❡ st❛t❡ ❛s ❢♦••♦✇s✿ u(s) = 3 -s✳ ❋✐♥❛••②✱ t❤❡ tr❛♥s✐t✐♦♥ ♠❛tr✐① ♦❢ t❤❡ ▼❛r❦♦✈ ❝❤❛✐♥ ♦❢ ♣r✐✈❛t❡ st❛t❡s ♦❢ ❡❛❝❤ ♣•❛②❡r ✐s

  ❞r✐✈❡r ✐s ❛ss✉♠❡❞ t♦ ❞r✐✈❡ β t✐♠❡s ❢❛st❡r t❤❛♥ ❛ ❣❡♥t•❡ ❞r✐✈❡r✳ ❯t✐•✐t✐❡s ❆ ❝❛r t❤❛t ❣♦❡s β t✐♠❡ ❢❛st❡r t❤❛♥ ❛♥♦t❤❡r ❝❛r✱ tr❛✈❡rs❡s t❤❡ ✉♥✐t ♦❢ ❞✐st❛♥❝❡ ❛t ❛ t✐♠❡ t❤❛t ✐s β t✐♠❡s s❤♦rt❡r✳ ❚❤✉s t❤❡ ❛✈❡r❛❣❡ ❞❛✐•② ❞❡•❛② ✐t ❡①♣❡r✐❡♥❝❡s ✐s β t✐♠❡s s❤♦rt❡r✳ ❲❡ ❛ss✉♠❡ t❤❛t ❛t ❛ ❞❛② ❞✉r✐♥❣ ✇❤✐❝❤ ❛ ❝❛r ❞r✐✈❡s ❢❛st✱ ✐t s♣❡♥❞s ✶✴β ♦❢ t❤❡ t✐♠❡ t❤❛t t❤❡ ♦t❤❡rs ❞♦✳ ■t ✐s t❤❡♥ r❡❛s♦♥❛❜•❡

  ❛ss ❝❛♥ ❜❡ ❝❤❛r❛❝t❡r✐③❡❞ ❜② ❛ s♦✉r❝❡✲❞❡st✐♥❛t✐♦♥ ♣❛✐r✱ ♦r ❜② ❛ ✈❡❤✐❝•❡ t②♣❡ ✭❝❛r✱ ♣❡❞❡str✐❛♥ ♦r ❜✐❝②❝•❡✮✳ ■♥ ❝♦♥tr❛st t♦ t❤❡ tr❛✣❝ ❛ss✐❣♥♠❡♥t ♣r♦❜•❡♠✱ t❤❡ ❝•❛ss ♦❢ ❛ ♣•❛②❡r ✐♥ ♦✉r s❡tt✐♥❣ ❝❛♥ ❝❤❛♥❣❡ ✐♥ t✐♠❡✳ ❚r❛♥s✐t✐♦♥ ♣r♦❜❛❜✐•✐t✐❡s t❤❛t ❣♦✈❡r♥ t❤✐s ❝❤❛♥❣❡ ♠❛② ❞❡♣❡♥❞ ♥♦t ♦♥•② ♦♥ t❤❡ ✐♥❞✐✈✐❞✉❛•✬s st❛t❡✱ ❜✉t ❛•s♦ ♦♥ t❤❡ ❢r❛❝t✐♦♥ ♦❢ ♣•❛②❡rs t❤❛t ❛r❡ ✐♥ ❡❛❝❤ ✐♥❞✐✲ ✈✐❞✉❛• st❛t❡ ❛♥❞ t❤❛t ✉s❡ ❞✐✛❡r❡♥t ❛❝t✐♦♥s✳ ❋✉rt❤❡r♠♦r❡✱ t❤❡s❡ tr❛♥s✐t✐♦♥s ❛r❡ ❝♦♥tr♦••❡❞ ❜② t❤❡ ♣•❛②❡r✳ ❆ str❛t❡❣② ♦❢ ❛ ♣•❛②❡r ♦❢ ❛ ❣✐✈❡♥ ❝•❛ss ✐♥ t❤❡ ❝•❛ss✐❝❛• tr❛✣❝ ❛ss✐❣♥♠❡♥t ♣r♦❜•❡♠ ❝❛♥ ❜❡ ✐❞❡♥t✐✜❡❞ ❛s t❤❡ ♣r♦❜❛❜✐•✐t② ✐t ✇♦✉•❞ ❝❤♦♦s❡ ❛ ❣✐✈❡♥ ❛❝t✐♦♥ ✭♣❛t❤✮ ❛♠♦♥❣ t❤♦s❡ ❛✈❛✐•❛❜•❡ t♦ ✐ts ❝•❛ss ✭♦r ✐ts ✏st❛t❡✑✮✳ ❚❤❡ ❞❡✜♥✐t✐♦♥ ♦❢ ❛ str❛t❡❣② ✐♥ ♦✉r ❝❛s❡ ✐s s✐♠✐•❛r✱ ❡①❝❡♣t t❤❛t ♥♦✇ t❤❡ ♣r♦❜❛❜✐•✐t② ❢♦r ❝❤♦♦s✐♥❣ ❞✐✛❡r❡♥t ❛❝t✐♦♥s s❤♦✉•❞ ❜❡ s♣❡❝✐✜❡❞ ♥♦t •✉st ✐♥ ♦♥❡ st❛t❡✳ ✾ ❆❝❦♥♦✇•❡❞❣❡♠❡♥ts ❲❡ ✇♦✉•❞ •✐❦❡ t♦ t❤❛♥❦ t✇♦ ❛♥♦♥②♠♦✉s r❡❢❡r❡❡s ❢♦r s✉❣❣❡st✐♥❣ s♦♠❡ ✐♠♣♦rt❛♥t ❝❤❛♥❣❡s ✇❤✐❝❤ ❤❡•♣❡❞ ✉s t♦ ✐♠♣r♦✈❡ t❤❡ ♠❛♥✉s❝r✐♣t ❛♥❞ ❆♥❞r③❡• ❙✳ ◆♦✇❛❦ ❢♦r s♦♠❡ •✐t❡r❛t✉r❡ s✉❣❣❡st✐♦♥s✳ ❚❤❡ ✇♦r❦ ♦❢ t❤❡ s❡❝♦♥❞ ❛✉t❤♦r ❤❛s ❜❡❡♥ ♣❛rt✐❛••② s✉♣♣♦rt❡❞ ❜② t❤❡ ❊✉r♦♣❡❛♥ ❈♦♠♠✐ss✐♦♥ ✇✐t❤✐♥ t❤❡ ❢r❛♠❡✇♦r❦ ♦❢ t❤❡ ❈❖◆✲ •❆❙ ♣r♦•❡❝t ❋P✼✲■❈❚✲✷✵✶✶✲✽✲✸✶✼✻✼✷✳ |❡❢❡r❡♥❝❡s ✶✳ ❲❛r❞r♦♣✱ ❏✳•✳✿ ❙♦♠❡ t❤❡♦r❡t✐❝❛• ❛s♣❡❝ts ♦❢ r♦❛❞ tr❛✣❝ r❡s❡❛r❝❤✳ Pr♦❝✳ ■♥st✳ ❈✐✈✳ ❊♥❣✳ ✷✱ ✸✷✺✕✸✼✽ ✭✶✾✺✷✮ ✷✳ ❍❛✉r✐❡✱ ❆✳✱ ▼❛r❝♦tt❡✱ P✳✿ ❖♥ t❤❡ r❡•❛t✐♦♥s❤✐♣ ❜❡t✇❡❡♥ ◆❛s❤✲❈♦✉r♥♦t ❛♥❞ ❲❛r❞r♦♣ ❡q✉✐✲ •✐❜r✐❛✳ ◆❡t✇♦r❦s ✶✺✭✸✮✱ ✷✾✺✕✸✵✽ ✭✶✾✽✺✮ ✸✳ ❇♦r❦❛r✱ ❱✳❙✳✿ ❈♦♦♣❡r❛t✐✈❡ ❞②♥❛♠✐❝s ❛♥❞ ❲❛r❞r♦♣ ❡q✉✐•✐❜r✐❛✳ ❙②st❡♠s ❈♦♥tr♦• ▲❡tt❡rs ✺✽✭✷✮✱ ✾✶✕✾✸ ✭✷✵✵✾✮ ✹✳ ▼❛②♥❛r❞ ❙♠✐t❤✱ ❏✳✿ •❛♠❡ ❚❤❡♦r② ❛♥❞ t❤❡ ❊✈♦•✉t✐♦♥ ♦❢ ❋✐❣❤t✐♥❣✳ ■♥✿ ▼❛②♥❛r❞ ❙♠✐t❤✱ ❏✳ ✭❡❞✳✮✿ ❖♥ ❊✈♦•✉t✐♦♥✱ ♣♣✳ ✽✕✷✽✳ ❊❞✐♥❜✉r❣❤ ❯♥✐✈❡rs✐t② Pr❡ss ✭✶✾✼✷✮ ✺✳ ❈r❡ss♠❛♥✱ |✳✿ ❊✈♦•✉t✐♦♥❛r② ❉②♥❛♠✐❝s ❛♥❞ ❊①t❡♥s✐✈❡ ❋♦r♠ •❛♠❡s✳ ▼■❚ Pr❡ss✱ ❈❛♠✲ ❜r✐❞❣❡✱ ▼❆ ✭✷✵✵✸✮ ✻✳ ❱✐♥❝❡♥t✱ ❚✳■✳✱ ❇r♦✇♥✱ ❏✳❙✳✿ ❊✈♦•✉t✐♦♥❛r② •❛♠❡ ❚❤❡♦r②✱ ◆❛t✉r❛• ❙❡•❡❝t✐♦♥ ❛♥❞ ❉❛r✇✐♥✐❛♥ ❉②♥❛♠✐❝s✳ ❈❛♠❜r✐❞❣❡ ❯♥✐✈❡rs✐t② Pr❡ss✱ ◆❡✇ (♦r❦ ✭✷✵✵✺✮ ✼✳ ❏♦✈❛♥♦✈✐❝✱ ❇✳✱ |♦s❡♥t❤❛•✱ |✳❲✳✿ ❆♥♦♥②♠♦✉s ❙❡q✉❡♥t✐❛• •❛♠❡s✳ ❏♦✉r♥❛• ♦❢ ▼❛t❤❡♠❛t✐❝❛• ❊❝♦♥♦♠✐❝s ✶✼✱ ✼✼✕✽✼ ✭✶✾✽✽✮ ✽✳ ❇❡r❣✐♥✱ ❏✳✱ ❇❡r♥❤❛r❞t✱ ❉✳✿ ❆♥♦♥②♠♦✉s s❡q✉❡♥t✐❛• ❣❛♠❡s ✇✐t❤ ❛❣❣r❡❣❛t❡ ✉♥❝❡rt❛✐♥t②✳ ❏♦✉r✲ ♥❛• ♦❢ ▼❛t❤❡♠❛t✐❝❛• ❊❝♦♥♦♠✐❝s ✷✶✱ ✺✹✸✕✺✻✷ ✭✶✾✾✷✮ ✾✳ ❇❡r❣✐♥✱ ❏✳✱ ❇❡r♥❤❛r❞t✱ ❉✳✿ ❆♥♦♥②♠♦✉s ❙❡q✉❡♥t✐❛• •❛♠❡s✿ ❊①✐st❡♥❝❡ ❛♥❞ ❈❤❛r❛❝t❡r✐③❛t✐♦♥ ♦❢ ❊q✉✐•✐❜r✐❛✳ ❊❝♦♥♦♠✐❝ ❚❤❡♦r② ✺✭✸✮✱ ✹✻✶✕✽✾ ✭✶✾✾✺✮ ✶✵✳ ❙•❡❡t✱ ❈✳✿ ▼❛r❦♦✈ ♣❡r❢❡❝t ❡q✉✐•✐❜r✐❛ ✐♥ ✐♥❞✉str✐❡s ✇✐t❤ ❝♦♠♣•❡♠❡♥t❛r✐t✐❡s✳ ❊❝♦♥♦♠✐❝ ❚❤❡♦r② ✶✼✭✷✮✱ ✸✼✶✕✸✾✼ ✭✷✵✵✶✮ ✶✶✳ ❈❤❛❦r❛❜❛rt✐✱ ❙✳❑✳✿ P✉r❡ str❛t❡❣② ▼❛r❦♦✈ ❡q✉✐•✐❜r✐✉♠ ✐♥ st♦❝❤❛st✐❝ ❣❛♠❡s ✇✐t❤ ❛ ❝♦♥✲ t✐♥✉✉♠ ♦❢ ♣•❛②❡rs✳ ❏✳ ▼❛t❤✳ ❊❝♦♥♦♠✳ ✸✾✭✼✮✱ ✻✾✸ï➾➼✲✼✷✹ ✭✷✵✵✸✮ ✶✷✳ ❆❞•❛❦❤❛✱ ❙✳✱ ❏♦❤❛r✐✱ |✳✿ ▼❡❛♥ ❋✐❡•❞ ❊q✉✐•✐❜r✐✉♠ ✐♥ ❉②♥❛♠✐❝ •❛♠❡s ✇✐t❤ ❙tr❛t❡❣✐❝ ❈♦♠♣•❡♠❡♥t❛r✐t✐❡s✳ ❖♣❡r❛t✐♦♥s |❡s❡❛r❝❤✱ ✻✶✭✹✮✱ ✾✼✶✕✾✽✾ ✭✷✵✶✸✮ ✶✸✳ •r❡❡♥✱ ❊✳✿ ◆♦♥❝♦♦♣❡r❛t✐✈❡ Pr✐❝❡ ❚❛❦✐♥❣ ✐♥ ▲❛r❣❡ ❉②♥❛♠✐❝ ▼❛r❦❡ts✳ ❏♦✉r♥❛• ♦❢ ❊❝♦✲ ♥♦♠✐❝ ❚❤❡♦r② ✷✷✱ ✶✺✺✕✶✽✶ ✭✶✾✽✵✮ ✶✹✳ •r❡❡♥✱ ❊✳✿ ❈♦♥t✐♥✉✉♠ ❛♥❞ ❋✐♥✐t❡✕P•❛②❡r ◆♦♥❝♦♦♣❡r❛t✐✈❡ ▼♦❞❡•s ♦❢ ❈♦♠♣❡t✐t✐♦♥✳ ❊❝♦♥♦♠❡tr✐❝❛ ✺✷✱ ✾✼✺✕✾✾✸ ✭✶✾✽✹✮ ✶✺✳ ❍♦✉s♠❛♥✱ ❉✳✿ ■♥✜♥✐t❡ P•❛②❡r ◆♦♥❝♦♦♣❡r❛t✐✈❡ •❛♠❡s ❛♥❞ t❤❡ ❈♦♥t✐♥✉✐t② ♦❢ t❤❡ ◆❛s❤ ❊q✉✐•✐❜r✐✉♠ ❈♦rr❡s♣♦♥❞❡♥❝❡✳ ▼❛t❤❡♠❛t✐❝s ♦❢ ❖♣❡r❛t✐♦♥s |❡s❡❛r❝❤ ✶✸✱ ✹✽✽✕✹✾✻ ✭✶✾✽✽✮ ✶✻✳ ❙❛❜♦✉r✐❛♥✱ ❍✳✿ ❆♥♦♥②♠♦✉s r❡♣❡❛t❡❞ ❣❛♠❡s ✇✐t❤ ❛ •❛r❣❡ ♥✉♠❜❡r ♦❢ ♣•❛②❡rs ❛♥❞ r❛♥❞♦♠ ♦✉t❝♦♠❡s✳ ❏♦✉r♥❛• ♦❢ ❊❝♦♥♦♠✐❝ ❚❤❡♦r② ✺✶✭✶✮✱ ✾✷✕✶✶✵ ✭✶✾✾✵✮ ✶✼✳ ❑r✉s❡••✱ P✳✱ ❙♠✐t❤✱ ❆✳❆✳ ❏r✳✿ ■♥❝♦♠❡ ❛♥❞ ❲❡❛•t❤ ❍❡t❡r♦❣❡♥❡✐t② ✐♥ t❤❡ ▼❛❝r♦❡❝♦♥♦♠②✳ ❏♦✉r♥❛• ♦❢ P♦•✐t✐❝❛• ❊❝♦♥♦♠② ✶✵✻✱ ✽✻✼ï➾➼✲✽✾✻ ✭✶✾✾✽✮ ✶✽✳ ❍♦♣❡♥❤❛②♥✱ ❍✳❆✳✿ ❊♥tr②✱ ❡①✐t✱ ❛♥❞ ✜r♠ ❞②♥❛♠✐❝s ✐♥ •♦♥❣ r✉♥ ❡q✉✐•✐❜r✐✉♠✳ ❊❝♦♥♦♠❡tr✐❝❛ ✻✵✭✺✮✱ ✶✶✷✼✲✶✶✺✵ ✭✶✾✾✷✮